Cod sursa(job #2197266)

Utilizator lucaperjuLuca Perju Verzotti lucaperju Data 21 aprilie 2018 16:27:15
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in ("carnati.in");
ofstream out ("carnati.out");
struct ura{
    int t,p;
}v[2002];
int d[2002],n,c;
bool cmp (ura a, ura b)
{
    if(a.t<=b.t)
        return true;
    return false;
}
int sum (int val)
{
    int mx=-99999999;
    if(v[1].p>=val)
        d[1]=max(0,v[1].p-c);
    else
        d[1]=0;
    for(int i=2;i<=n;i++)
    {
        if(v[i].p>=val)
            d[i]=max(d[i-1]-(v[i].t-v[i-1].t)*c+val,val-c);
        else
            d[i]=max(0,d[i-1]-(v[i].t-v[i-1].t)*c);
        if(d[i]>mx)
            mx=d[i];
    }
    return mx;
}
int main()
{
    int i,a,mx=-99999999;
    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++)
    {
        a=sum(v[i].p);
        if(a>mx)
            mx=a;
    }
    out<<mx;
    return 0;
}