Cod sursa(job #2704339)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 10 februarie 2021 12:47:08
Problema Carnati Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

using namespace std;

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

int t[N], p[N];

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

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

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

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

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