Cod sursa(job #1254197)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 2 noiembrie 2014 12:19:52
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 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[20005];
long long n,c,sol[20005],best = -1000000000;

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()
{
    sol[0] = -10000;
    v[0].timp = v[0].pret = -10;
    sort(v,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);
                if(sol[j] < 0 )
                    sol[j] = max(sol[j-1]-(v[j].timp-v[j-1].timp)*c,(long long)0);
                best = max(best,sol[j]);
            }
            else
                sol[j] = max(sol[j-1]-(v[j].timp-v[j-1].timp)*c,(long long)0);
    }
    out<<best;
    out.close();
}

int main()
{

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