Cod sursa(job #2712364)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 25 februarie 2021 18:05:56
Problema Carnati Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("carnati.in");
ofstream fout("carnati.out");
int n, c;
long long ans = INT_MIN;
vector <pair <int, int> > v;
int main()
{
    fin >> n >> c;
    for (int i = 0; i < n; ++i) {
        int x, y;
        fin >> x >> y;
        v.push_back({x, y});
    }

    sort(v.begin(), v.end());

    for (int i = 0; i < n; ++i) {
        long long suma = 0, smin = 0, maxi = INT_MIN, k = 1;
        int nr = v[i].second;
        for (int j = 0; j < n; ++j) {
            if (v[j].second >= nr)
                suma += nr;
            if (k == 1) {
                suma -= c;
            }
            else {
                suma -= (v[j].first - v[j-1].first) * c;
            }
            maxi = max(maxi, suma - smin);
            if (smin > suma) {
                smin = suma;
                k = 0;
            }

            k++;
        }

        if (maxi > ans)
            ans = maxi;
    }

    fout << ans;
    return 0;
}