Cod sursa(job #3265983)

Utilizator RuxandraPro12_Metehau Ruxandra Maria RuxandraPro12_ Data 4 ianuarie 2025 18:18:38
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

int n, c, profit[2005];
pair <int, int> a[2005];

int main() {
    fin >> n >> c;
    for (int i = 1; i <= n; i++)
        fin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    ///for (int i = 1; i <= n; i++)
       /// fout << a[i].first << " " << a[i].second << "\n";
    int maxi_profit = -1e9;
    for (int i = 1; i <= n; i++) {
        int copie = a[i].second;
        for (int j = 1; j <= n; j++) {
            int dist_cost = (a[j].first - a[j - 1].first) * c;
            if (a[j].second >= copie)
                profit[j] = max(profit[j - 1] - dist_cost + copie, copie - c);
            else
                profit[j] = max(profit[j - 1] - dist_cost, 0 - c);
            maxi_profit = max(maxi_profit, profit[j]);
        }
    }
    fout << maxi_profit;
    return 0;
}