Cod sursa(job #1786677)

Utilizator c0mradec0mrade c0mrade Data 23 octombrie 2016 14:27:32
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

int n, c, ans;

struct man
{
    int t, p;
}v[2010];

bool cmp(man a, man b)
{
    return a.t < b.t;
}

int main()
{
    fin >> n >> c;
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i].t >> v[i].p;
    }

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

    v[0].t = -11;

    for(int i = 1; i <= n; ++i)
    {
        int mx = v[i].p;
        int best = 0;

        for(int j = 1; j <=n; ++j)
        {
            int newGain = 0;
            if(v[j].p >= mx)
                newGain = mx;
            if(best - c * (v[j].t - v[j-1].t) > 0)
                best += newGain - c * (v[j].t - v[j-1].t);
            else
                best = newGain - c;
            ans = max(ans, best);
        }
    }

    fout << ans;

    return 0;
}