Cod sursa(job #2602938)

Utilizator eugen5092eugen barbulescu eugen5092 Data 18 aprilie 2020 10:41:20
Problema Heavy metal Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
using namespace std;
ifstream ci("heavymetal.in");
ofstream cou("heavymetal.out");
struct date{
    int a,b;
};
//nr de ore mx pana la ora i
int dp[1000],n;
date v[100010];

bool cmp(date a,date b){
    return a.b<b.b;
}
void citire(){
    int i;
    ci>>n;
    for(i=1;i<=n;i++){
        ci>>v[i].a>>v[i].b;
    }
    sort(v+1,v+n+1,cmp);
}

void rez(){
    int i,mx,p,a,b,sol=0;
    for(i=1;i<=n;i++){
        //dp[v[i].b]=v[i].b-v[i].a;
        mx=0;
        a=v[i].a;
        b=v[i].b;
        for(int j=b;j>=1;j--){
            if(j<=a){
                mx=max(mx,dp[j]+b-a);
            }else{
                mx=max(mx,dp[j]);
            }
        }
        if(dp[b]==0){
            dp[b]=mx;
        }else{
            dp[b]=max(dp[b],mx);
        }
    }
    for(i=1;i<=1001;i++){
        //cout<<dp[i]<<" ";
        sol=max(sol,dp[i]);
    }
    //cout<<"\n";
    cou<<sol;

}

int main()
{
    citire();
    rez();
    return 0;
}