Cod sursa(job #1036856)

Utilizator andrettiAndretti Naiden andretti Data 19 noiembrie 2013 17:52:16
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include<stdio.h>
#include<algorithm>
#define maxn 2005
#define inf 0x3f3f3f3f
using namespace std;

struct buy{int t,p;} a[maxn];
int n,c,sol=-inf;

void read()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
      scanf("%d%d",&a[i].t,&a[i].p);
}

bool cmp(const buy &x,const buy &y){
    return x.t<y.t;
}

void solve()
{
    int sum,a2;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        sum=a[1].p; if(a[1].p<a[i].p) sum=0;
        sol=max(sol,sum-c);
        for(int j=2;j<=n;j++)
        {
            a2=0;
            sum-=(a[j].t-a[j-1].t)*c;
            if(a[j].p>=a[i].p) sum+=a[i].p,a2=a[i].p;
            sol=max(sol,max(sum-c,a2));
            if(sum<a2) sum=a2;
        }
    }
}

int main()
{
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);

    read();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}