Cod sursa(job #2170433)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 15 martie 2018 00:49:50
Problema Heavy metal Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.48 kb
#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
ifstream in("heavymetal.in");
ofstream out("heavymetal.out");
pair<int,int> v[100001];
int dp[100001];
int main(){
    int n,i,j=1;
    in>>n;
    for(i=1; i<=n; ++i)
        in>>v[i].s>>v[i].f;
    sort(v+1, v+n+1);
    for(i=1; i<=v[n].f; ++i){
        dp[i]=dp[i-1];
        while(v[j].f==i)
            dp[i]=max(dp[i],dp[v[j].s]+v[j].f-v[j++].s);
    }
    out<<dp[v[n].f];
    return 0;
}