Cod sursa(job #2929822)

Utilizator AleXutzZuDavid Alex Robert AleXutzZu Data 26 octombrie 2022 22:14:54
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <algorithm>

int main() {
    std::ifstream input("carnati.in");
    std::ofstream output("carnati.out");

    int n, c;

    input >> n >> c;

    std::pair<int, int> clients[2000] = {};

    for (int i = 0; i < n; ++i) input >> clients[i].first >> clients[i].second;

    std::sort(clients, clients + n, [](const std::pair<int, int> &a, const std::pair<int, int> &b) {
        return a.first < b.first;
    });

    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        int max = clients[i].second;

        long long a = (max <= clients[0].second ? max : 0) - c;

        for (int j = 1; j < n; ++j) {
            long long paid = max <= clients[j].second ? max : 0;
            long long candidate = std::max(a + paid - c * (clients[j].first - clients[j - 1].first), paid - c);
            ans = std::max(ans, candidate);
            a = candidate;
        }
    }

    output << ans;

    return 0;
}