Cod sursa(job #910029)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 10 martie 2013 18:25:37
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<fstream>
#include<algorithm>
#define NMAX 2010

using namespace std;

ifstream f("carnati.in");
ofstream g("carnati.out");

struct omustean
{
    int t;
    long long p;
}a[NMAX];

int n;
long long best[NMAX], C;

void Citeste()
{
    int i;

    f>>n>>C;

    for (i=1; i<=n; ++i)
        f>>a[i].t>>a[i].p;
}

int cmp(omustean A, omustean B)
{
    return A.t<B.t;
}

void Solve()
{
    int i, j;
    long long val, sol=-1;

    sort(a+1, a+n+1, cmp);

    for (i=1; i<=n; ++i)
    {
        val=a[i].p;

        for (j=1; j<=n; ++j)
        {
            if (val<=a[j].p) best[j]=max(best[j-1]+val-C*(a[j].t-a[j-1].t), val-C);
            else best[j]=max(best[j-1]-C*(a[j].t-a[j-1].t), -C);
            sol=max(best[j], sol);
        }
    }

    g<<sol<<"\n";
}

int main()
{
    Citeste();

    Solve();

    f.close();
    g.close();
    return 0;
}