Cod sursa(job #2530549)

Utilizator vladth11Vlad Haivas vladth11 Data 24 ianuarie 2020 22:03:29
Problema Carnati Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"

using namespace std;
typedef long long ll;
int n,c,timp,minim = 2e9;
vector <int> t[1501];
vector <int> teste;
int v[1501];
int pretul(int x){
    int best = 0,sum = 0;
    for(int i = minim;i <= timp;i++){
        v[i] = -c;
        for(int j = t[i].size() - 1;j >= 0;j--){
            if(t[i][j] >= x){
                v[i] += x;
            }else{
                break;
            }
        }
        sum += v[i];
        if(sum > best){
            best = sum;
        }
        if(sum < 0)
            sum = 0;
    }
    return best;
}
int main()
{
    ifstream cin(".in");
    ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> c;
    for(int i = 1;i <= n;i++){
        int x,y;
        cin >> x >> y;
        minim = min(minim,x);
        timp = max(timp,x);
        t[x].push_back(y);
        teste.push_back(y);
    }
    for(int i = minim;i <= timp;i++)
        sort(t[i].begin(),t[i].end(),less <int> ());
    int maxim = 0;
    for(int i = 0;i < n;i++){
        maxim = max(maxim,pretul(teste[i]));
    }
    cout << maxim;
    return 0;
}