<p>You want to schedule a list of jobs in <code>d</code> days. Jobs are dependent (i.e To work on the <code>i<sup>th</sup></code> job, you have to finish all the jobs <code>j</code> where <code>0 &lt;= j &lt; i</code>).</p>

<p>You have to finish <strong>at least</strong> one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the <code>d</code> days. The difficulty of a day is the maximum difficulty of a job done on that day.</p>

<p>You are given an integer array <code>jobDifficulty</code> and an integer <code>d</code>. The difficulty of the <code>i<sup>th</sup></code> job is <code>jobDifficulty[i]</code>.</p>

<p>Return <em>the minimum difficulty of a job schedule</em>. If you cannot find a schedule for the jobs return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/01/16/untitled.png" style="width: 365px; height: 370px;" />
<pre>
<strong>Input:</strong> jobDifficulty = [6,5,4,3,2,1], d = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> jobDifficulty = [9,9,9], d = 4
<strong>Output:</strong> -1
<strong>Explanation:</strong> If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> jobDifficulty = [1,1,1], d = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> The schedule is one job per day. total difficulty will be 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= jobDifficulty.length &lt;= 300</code></li>
	<li><code>0 &lt;= jobDifficulty[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= d &lt;= 10</code></li>
</ul>

class SGT_PU{
    // segement tree point update 
    // like fenwick tree
    // this is for 0 based indexing so idx=0
public:
    vector<int> seg;
    SGT_PU(int n){
        seg.resize(4*n+1);
    }
    void build(int idx,int low,int high,vector<int> &arr){
        if(low==high){
            seg[idx]=arr[low];
            return;
        }
        int mid=low+(high-low)/2;
        build(2*idx+1,low,mid,arr);
        build(2*idx+2,mid+1,high,arr);
        seg[idx]=max({seg[2*idx+1],seg[2*idx+2]});
    }
    int query(int idx,int low,int high,int l,int r){
        // no overlap
        // l r low high , low high l r
        if(r<low or high<l) return INT_MIN;
        // completely overlap
        // l low high r
        if(low>=l and high<=r) return seg[idx];
        // partially overlap
        int mid=low+(high-low)/2;
        int left=query(2*idx+1,low,mid,l,r);
        int right=query(2*idx+2,mid+1,high,l,r);
        return max({left,right});
    }
    void update(int idx,int low,int high,int i,int val){
        if(low==high){
            seg[idx]=val;
            return;
        }
        int mid=low+(high-low)/2;
        if(i<=mid){
            update(2*idx+1,low,mid,i,val);
        }else{
            update(2*idx+2,mid+1,high,i,val);
        }
        seg[idx]=max({seg[2*idx+1],seg[2*idx+2]});
    }
};
class Solution {
public:
    int n;
    long long dp[302][12];
    long long solve(int prev,vector<int> &arr,int d,SGT_PU &sg){
        if(d<=0 and prev>=n) return 0;
        if(prev>=n or d<=0) return INT_MAX;
        if(dp[prev][d]!=-1) return dp[prev][d];
        long long mn=INT_MAX;
        for(int i=prev+1;i<=n;i++){
            mn=min(mn,sg.query(0,0,n-1,prev,i-1)+solve(i,arr,d-1,sg));
        }
        return dp[prev][d]=mn;
    }
    int minDifficulty(vector<int>& arr, int d) {
        n=arr.size();
        SGT_PU sg(n);
        sg.build(0,0,n-1,arr);
        memset(dp,-1,sizeof(dp));
        if(d>n) return -1;
        return solve(0,arr,d,sg);
    }
};
10900