Cod sursa(job #3325650)

Utilizator unomMirel Costel unom Data 25 noiembrie 2025 21:45:45
Problema Carnati Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

#define int long long

ifstream in("carnati.in");
ofstream out("carnati.out");
int n, c;
pair<int, int> v[2005];
int INF = (1LL << 60);

int solve(int cost)
{
    int ans = -INF;

    int sum = 0;

    for(int i = 1; i<=n; i++)
    {
        if(v[i].first > v[i - 1].first)
        {
            sum -= ((v[i].first - 1) - v[i - 1].first) * c;
        }

        if(sum < 0)
        {
            sum = 0;
        }

//        cout<<sum<<" ";

        if(v[i].first > v[i - 1].first)
        {
            sum -= c;
        }

        if(cost <= v[i].second)
        {
            sum += cost;
        }

//        cout<<sum<<'\n';

        ans = max(ans, sum);
    }
//    cout<<'\n';

//    cout<<ans;

    return ans;
}

signed main()
{
    in>>n>>c;

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

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

    int ans = -INF;
    for(int i = 1; i<=n; i++)
    {
        ans = max(ans, solve(v[i].second));
    }

    out<<ans;

    return 0;
}