Cod sursa(job #1776749)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 11 octombrie 2016 19:42:58
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <cstdio>
#include <algorithm>
using namespace std;
int n,c;
struct CLIENT
{
    int t,p;
} v[2005];
bool cmp(CLIENT a,CLIENT b)
{
    return a.t<b.t;
}
int d[2005],ans=-1;
void check(int arg)
{
    for(int i=1; i<=n; i++)
    {
        if(v[i].p>=arg) d[i]=max(arg-c,d[i-1]+arg-c*(v[i].t-v[i-1].t));
        else d[i]=max(-c,d[i-1]-c*(v[i].t-v[i-1].t));
        ans=max(ans,d[i]);
    }
}
int main()
{
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);
    int i;
    scanf("%d%d",&n,&c);
    v[0].t=0;
    for(i=1; i<=n; i++) scanf("%d%d",&v[i].t,&v[i].p);
    sort(v+1,v+n+1,cmp);
    for(i=1; i<=n; i++) check(v[i].p);
    printf("%d\n",ans);
    return 0;
}