Cod sursa(job #3325653)

Utilizator unomMirel Costel unom Data 25 noiembrie 2025 21:50:00
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 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 = 0;

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

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

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

        ans = max(ans, sum);
    }

    ans -= c;

    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);

    v[0].first = v[1].first;

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

    out<<ans;

    return 0;
}