Cod sursa(job #2497985)

Utilizator MariusblockMoga Marius-Ioan Mariusblock Data 23 noiembrie 2019 13:10:45
Problema Heavy metal Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <bits/stdc++.h>

using namespace std;

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

struct formatie{
    int a,b;
};

const int inf = 1000000003;
formatie f[100004];
int DP[100004];
int DPstart[100004];

bool cmp(formatie x,formatie y){
    if(x.b > y.b){
        return 1;
    }else{
        return 0;
    }
}

int main()
{
    int n,i,aux,j;
    fin>>n;
    for(i = 1; i <= n ; i++){
        fin>>f[i].a>>f[i].b;
    }
    sort(f+1,f+n+1,cmp);
    for(i = 1; i <= n; i++){
        aux = 0;
        j = i-1;
        while(!aux && j){
            if(DPstart[j] >= f[i].b){
                aux = DP[j];
            }
            j--;
        }
        if(DP[i-1] < aux + f[i].b - f[i].a){
            DP[i] = aux + f[i].b - f[i].a;
            DPstart[i] = f[i].a;
        }else{
            DP[i] = DP[i-1];
            DPstart[i] = DPstart[i-1];
        }
    }
    fout<<DP[n]<<endl;
    return 0;
}