Cod sursa(job #961270)

Utilizator primulDarie Sergiu primul Data 11 iunie 2013 20:28:16
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");
const int N = 2005;
struct carnat{
    int t,p;
};
carnat v[N];
int n,C,pret,aux,s,smax;
bool cmp(carnat a,carnat b){
    return a.t<b.t;
}
int main(){
    int i,j;
    in>>n>>C;
    for(i=1;i<=n;i++) in>>v[i].t>>v[i].p;
    sort(&v[1],&v[n+1],cmp);
    for(i=1;i<=n;i++) if(v[i].p>smax) smax=v[i].p;
    for(i=1;i<=n;i++){
        pret=v[i].p;
        s=0;
            if(v[1].p>=pret) aux=pret;
            else aux=0;
        s+=aux;
        for(j=2;j<=n;j++){
            aux=-(v[j].t-v[j-1].t)*C;
            s+=aux;
            if(s<0) s=0;
            if(v[j].p>=pret) aux=pret;
            else aux=0;
            s+=aux;
            if(s>smax) smax=s;
        }
    }
    out<<smax-C;
    return 0;
}