Cod sursa(job #1358113)

Utilizator robx12lnLinca Robert robx12ln Data 24 februarie 2015 13:03:45
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include<fstream>
#include<algorithm>
#define profit second
#define time first
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");
pair<int,int>p[2005];
int i,n,c,v[2005],j,val,maxim;
int max(int a,int b){
    if(a<=b){
        return b;
    }
    return a;
}
int main(){
    fin>>n>>c;
    for(i=1;i<=n;i++){
        fin>>p[i].time>>p[i].profit;
    }
    sort(p+1,p+n+1);
    p[0].time=p[0].profit=-10;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            val=p[i].profit;
            if(p[j].profit<val){
                val=0;
            }
            v[j]=max(v[j-1]-(p[j].time-p[j-1].time)*c+val,val-c);
            if(maxim<v[j]){
                maxim=v[j];
            }
        }
    }
    fout<<maxim;
    return 0;
}