Cod sursa(job #1786669)

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

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

int n, c, ans;

pair<int, int> v[2010];

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

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

    v[0].first = -1;

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

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

    fout << ans;

    return 0;
}