Cod sursa(job #2704341)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 10 februarie 2021 12:51:57
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <fstream>
#include <algorithm>

using namespace std;

const long long N = 2000;
const long long INF = 1 << 30;

struct P {
    long long t;
    long long p;
    bool operator<(const P& alt) const {
        return t < alt.t;
    }
} v[N];

int main() {
    ifstream in("carnati.in");
    ofstream out("carnati.out");

    long long n, c, s, d, maxst, maxdr, rez = -INF;
    in >> n >> c;
    for (long long i = 0; i < n; ++i)
        in >> v[i].t >> v[i].p;
    sort(v, v + n);
    for (long long i = 0; i < n; ++i) {
        //pretul curent v[i].p
        s = 0;
        maxst = -INF;
        for (long long j = i - 1; j >= 0; --j) {
            if (v[j].p >= v[i].p)
                s += v[i].p;
            d = (v[i].t - v[j].t) * c;
            maxst = max(maxst, s - d);
        }

        s = 0;
        maxdr = -INF;
        for (long long j = i; j < n; ++j) {
            if (v[j].p >= v[i].p)
                s += v[i].p;
            d = (v[j].t - v[i].t + 1) * c;
            maxdr = max(maxdr, s - d);
        }

        rez = max(rez, maxst + maxdr);
    }
    out << rez;

    in.close();
    out.close();
    return 0;
}