Cod sursa(job #2497997)

Utilizator AteveuPescaru Andrei Ateveu Data 23 noiembrie 2019 13:20:37
Problema Heavy metal Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 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 j = i;
            do{
                j--;
            }while(T[j].final >= T[i].start);
            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;
}