Cod sursa(job #1254156)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 2 noiembrie 2014 11:53:56
Problema Carnati Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");

struct om{
    long long pret;
     long long timp;
};

om v[2005];
long long n,c,sol[2005],best;

bool comp(om a,om b)
{

    return a.timp<b.timp;
}

void citire()
{

    in>>n>>c;
    for(int i = 1; i <= n ; i++)
        in>>v[i].timp>>v[i].pret;
    in.close();
}

void solve()
{
    v[0].timp = v[0].pret = -10;
    sort(v+1,v+n+1,comp);
    int i,j,p;
    for(i = 1; i <= n ; i++){
        p = v[i].pret;
        for(j = 1 ; j <= n ; j++)
            if(v[j].pret >= p){
                sol[j] = max(sol[j-1]-(v[j].timp-v[j-1].timp)*c+p,p-c);
                best = max(best,sol[j]);
            }
            else
                sol[j] = max(sol[j-1]-(v[j].timp-v[j-1].timp)*c,(long long)0);
    }
    if(best > 0)
    out<<best;
    else out<<0;
    out.close();
}

int main()
{

    citire();
    solve();
    return 0;
}