Cod sursa(job #2863640)

Utilizator TrabucMihaiTrabucMihai TrabucMihai Data 7 martie 2022 00:37:59
Problema Carnati Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.02 kb

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,best = -1e9;
vector<pair<int,int>> v;
int Smax(int x)
{
    int best = -1e9;
    int st = 0,inte = 0,inte2 = 0,s = 0;
    queue<int> q;
    for(int i = 0; i < v.size(); ++i)
    {
        if(v[i].second < x)
        {
            continue;
        }
        if(v[i].second >= x)
        {
            s += x;
            if(!inte) inte = v[i].first;
            inte2 = v[i].first;
        }
        int z = inte2 - inte + 1;
        int presum = s - z * m;
        best = max(best,presum);
        if(presum < 0) presum = s = 0,inte = inte2 = 0;
    }
    return best;
}
signed main()
{
    ifstream cin ("carnati.in");
    ofstream cout ("carnati.out");
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        int a,b;
        cin >> a >> b;
        v.push_back(make_pair(a,b));
    }
    sort(v.begin(),v.end());
    for(int i = 0;i < v.size(); ++i)
        best = max(best,Smax(v[i].second));
    cout << best;
}