Cod sursa(job #2498020)

Utilizator AteveuPescaru Andrei Ateveu Data 23 noiembrie 2019 13:35:47
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <algorithm>

#define final first
#define start second

using namespace std;
ifstream fin("heavymetal.in");
ofstream fout("heavymetal.out");

int DP[100005], f, s;
pair <int, int> T[100005];
int n;

void Read(){
    fin>>n;
    for(int i = 1; i <= n; i++){
        fin>>T[i].start>>T[i].final;
    }
    sort(T+1, T+1+n);
}

void Solve(){
    int Max = 0;
    for(int i = 1; i <= n; i++){
        if(f <= T[i].start){
            DP[i] = DP[i-1] + T[i].final - T[i].start;
        }
        else{
            int k = i;
            do{
                k--;
            }while(T[k].final >= T[i].start);
            for(int j = k; j > 0; j--)
                DP[i] = max(DP[i],DP[j] + T[i].final - T[i].start);
        }
        f = T[i].final;
        if(DP[i] > Max) Max = DP[i];
    }
    fout<<Max;
}

int main()
{
    Read();
    Solve();
    return 0;
}