Cod sursa(job #1904335)

Utilizator andru47Stefanescu Andru andru47 Data 5 martie 2017 14:38:25
Problema Carnati Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
vector < pair<int , int> > v;
int main()
{
    freopen("carnati.in","r",stdin);
    freopen("carnati.out","w",stdout);

    int n;
    long long c;
    scanf("%d %lld\n", &n, &c);

    for (int i = 1; i<=n; ++i)
    {
        int x , y;
        scanf("%d %d\n", &x, &y);
        v.push_back({x , y});
    }
    sort(v.begin(), v.end());
    long long maxy = 0LL;
    for (int i = 1; i<=n; ++i)
    {
        long long sum = 0LL,timp = v[0].first, pret = v[i].second;
        int ind = 0;
        for ( ; ind < n && v[ind].second < pret; ++ind);
        timp = v[ind].first;
        ind = -1;
        for (auto &it : v)
        {
            ++ind;
            if (it.second < pret)
                continue;
            int dift = it.first - timp;
            sum -= dift * c;
            sum += pret;
            sum -= c;
            timp = it.first + 1;
            maxy = max(maxy , sum);
            if (sum <= 0 && ind < n - 1)
                timp = v[ind + 1].first, sum = 0;;
        }
    }
    printf("%lld\n", maxy);
    return 0;

}