4 / 4
Feb 2022
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define inf 2e18
#define maxn 100005
#define mod 1000000007

struct order{
    int start,finish,value,index;
}orderlist[maxn];

bool cmp(order a,order b){
    return a.finish<b.finish;
}


signed main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin>>t;
    int dp[maxn];
    int prev[maxn];
    while(t--){
        memset(dp,0,sizeof(dp));
        memset(prev,0,sizeof(prev));
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>orderlist[i].start>>orderlist[i].finish>>orderlist[i].value;
        }
        sort(orderlist,orderlist+n,cmp);
        for(int i=1;i<=n;i++){
            orderlist[i].index=i;
        }
        for(int i=n;i>0;i--){
            for(int j=n-1;j>0;j--){
                if(orderlist[j].finish<=orderlist[i].start){
                    prev[i]=orderlist[j].index;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            dp[i]=max(dp[i-1],dp[prev[i]]+orderlist[i].value);
        }
        cout<<dp[n]<<endl;
    }
}
  • created

    Feb '22
  • last reply

    Feb '22
  • 3

    replies

  • 781

    views

  • 2

    users

  • 1

    link

The data for each order doesn’t include the finish time - it’s the start time, duration, and price.

When you’ve corrected that, try this test case:

5
19 9 17
19 3 5
10 14 15
15 13 19
0 16 3

My AC solution gives 20, your code gives 19.