Cod sursa(job #1904364)

Utilizator andru47Stefanescu Andru andru47 Data 5 martie 2017 14:53:17
Problema Carnati Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
using namespace std;
vector < pair<int , int> > v;
inline bool cmp(pair<int , int>a, pair<int , int> b)
{
    if (a.first > b.first)
        return false;
    else if (a.first == b.first && a.second < b.second)
        return false;
    return true;
}
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(), cmp);
    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;
        int cind = ind;
        ind = -1;
        for (auto &it : v)
        {
            ++ind;
            if (cind != ind && it.first == timp + 1)
                continue;
            if (it.second < pret)
                continue;
            int dift = it.first - timp;
            sum -= dift * c;
            if (sum <= 0)
                sum = 0;
            sum += pret;
            sum -= c;
            timp = it.first + 1;
            maxy = max(maxy , sum);
        }
    }
    printf("%lld\n", maxy);
    return 0;

}