Cod sursa(job #3342234)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 23 februarie 2026 14:24:27
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f ("carnati.in");
ofstream g ("carnati.out");

const int NMAX = 2000;
int N, C, sol = -1e9, secv;

struct client {
    int timp, pret;
    //
    bool operator < (const client &c) const {
        return timp < c.timp;
    }
};

client V[NMAX+1];

void citire() {
    f >> N >> C;
    for (int i=1; i<=N; i++)
        f >> V[i].timp >> V[i].pret;
    //
    sort(V+1, V+N+1);
}

void solve() {
    int X;
    //
    for (int k=1; k<=N; k++) {
        X = V[k].pret;
        secv = 0;
        for (int i=1; i<=N; i++) {
            int profit = (X <= V[i].pret) ? X : 0;

            if (secv == 0) {
                if (profit > C)
                    secv = profit;
            } else if (secv - (V[i].timp - V[i-1].timp) * C + profit > 0) {
                secv = secv - (V[i].timp - V[i-1].timp) * C + profit;
            } else if (profit > C)
                secv = profit;
            else
                secv = 0;
            //
            sol = max(sol, secv);
        }
    }
}

int main(){
    citire();
    solve();
    //
    g << sol - C;

    f.close();
    g.close();
    return 0;
}