Cod sursa(job #1645020)

Utilizator RaduToporanRadu Toporan RaduToporan Data 10 martie 2016 10:42:16
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");
long long n,c,ans=-1;
struct om
{
    long long p,t;
} O[2016];
bool cmp(om a, om b)
{
    return a.t < b.t;
}
long long calc(long long pret)
{
    long long ans=0, act=0,a=0;
   for(int i=1; i<=n; i++)
    {
        act=act-c*(O[i].t-O[i-1].t);
        if(act<0)act=0;
        if(O[i].p>=pret)act=act+pret;
        ans=max(ans,act-c);
    }
    return ans;
}
int main()
{
    in>>n>>c;
    for(int i=1; i<=n; i++)
        in>>O[i].t>>O[i].p;
    sort(O+1,O+n+1,cmp);
    for(int i=1; i<=n; i++)
        ans=max(ans,calc(O[i].p));
    out<<ans;
    return 0;
}