Cod sursa(job #2058875)

Utilizator wefgefAndrei Grigorean wefgef Data 6 noiembrie 2017 12:19:38
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <algorithm>
#include <iostream>
using namespace std;

const int MAX_N = 2000;
const int MAX_T = 1500;

int n, c;
int t[MAX_N], p[MAX_N];

long long v[MAX_T + 1];

long long solve(int price) {
    for (int i = 0; i <= MAX_T; ++i) {
        v[i] = -c;
    }
    for (int i = 0; i < n; ++i) {
        if (p[i] >= price) {
            v[t[i]] += price;
        }
    }
    long long sum = 0, sol = 0, bestSum = 0;
    for (int i = 0; i <= MAX_T; ++i) {
        sum += v[i];
        sol = max(sol, sum - bestSum);
        bestSum = min(bestSum, sum);
    }
    return sol;
}

int main() {
    freopen("carnati.in", "r", stdin);
    freopen("carnati.out", "w", stdout);
    cin >> n >> c;
    for (int i = 0; i < n; ++i) {
        cin >> t[i] >> p[i];
    }
    
    long long best = 0;
    for (int i = 0; i < n; ++i) {
        best = max(best, solve(p[i]));
    }
    cout << best << "\n";
}