Cod sursa(job #1732883)

Utilizator Moise_AndreiMoise Andrei Moise_Andrei Data 22 iulie 2016 20:57:48
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("carnati.in");
ofstream out("carnati.out");
const int maxn = 2005;
pair <int, int> v[maxn];
int p[maxn];
int n, c,mx;
int ac(int a)
{
    int ret = 0,s = 0;
    for(int i = 1; i <= n; i++)
    {
        int salariu = (v[i].first - v[i-1].first) * c;
        s = s - salariu;
        s = max(s, 0);
        if(a <= v[i].second)
            s += a;
        ret = max(ret, s - c);
    }
    return ret;
}
int main()
{
    in >> n >> c;
    for(int i = 1; i <= n; i++)
        in >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; i++)
        mx = max(mx, ac(v[i].second));
    out << mx << "\n";
    return 0;
}