Submission #573118

#	Time	Username	Problem	Language	Result	Execution time	Memory
573118		gcconure	Job Scheduling (CEOI12_jobs)	C++17	0 / 100	1067 ms	1996 KiB

jobs

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
int main(){
    ll t; cin >> t;
 
    for(ll tt = 0; tt < t; tt++){
        ll n; cin >> n;
 
        vector<pair<pair<ll,ll>,ll>> v;
        for(ll i =0; i < n; i++){
            ll a,b,c; cin >> a >> b >> c;
            v.push_back({{a,b},c});
        }
        
        sort(v.begin(), v.end());
        ll prev[n]; ll cur = -1; prev[0]=-1;
        for(ll i = 1; i < n; i++){
            while(cur<i and v[cur+1].first.second<v[i].first.first){
                cur++;
            }
            prev[i]=cur;
        }
 
        ll arr[n]; arr[0] = v[0].second;
        for(ll i = 1; i < n; i++){
            if(prev[i]==-1){
                arr[i]=max(arr[i-1],v[i].second);
                continue;
            }
            arr[i]=max(arr[prev[i]]+v[i].second,arr[i-1]);
        }
 
        cout << arr[n-1] << "\n";
    }
} 

• Subtask 1: 0 / 100