Cod sursa(job #1385592)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 12 martie 2015 09:18:23
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <fstream>
#include <algorithm>
#define nmax 2005
#define inf 1<<30
using namespace std;
ifstream f("carnati.in");
ofstream g("carnati.out");
int n,c,a[nmax],sol=-inf;
struct client{int t;int p;};
client v[nmax];

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

}
int solve(int k)
{
    int i,j,r=0;
    a[0]=-inf;
    for (i=1;i<=n;i++) {
        a[i]=max(a[i-1]-(v[i].t-v[i-1].t)*c,-c);
        if (v[i].p>=k)
            a[i]+=k;
        r=max(a[i],r);
    }
    return r;

}
int main()
{
    int i,j,p=0;
    f>>n>>c;
    for (i=1;i<=n;i++)
        f>>v[i].t>>v[i].p;
    sort(v+1,v+n+1,cmp);
    for (i=1;i<=n;i++)
        sol=max(sol,solve(v[i].p));
    g<<sol<<'\n';
    return 0;
}