Cod sursa(job #1125607)

Utilizator diana97Diana Ghinea diana97 Data 26 februarie 2014 18:39:42
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

int n, cost;
struct om {
    int timp, pret;
} v[2005];
int sol[2005];

void citeste () {
    f >> n >> cost;
    for (int i = 1; i <= n; i++) f >> v[i].timp >> v[i].pret;
}

inline int conditie (om a, om b) {
    return a.timp < b.timp;
}

void rezolva () {
    int maxim = -100;
    sol[0] = -100;
    int pret, G;
    for (int i = 1; i <= n; i++) {
        pret = v[i].pret;
        for (int j = 1; j <= n; j++) {
            if (v[j].pret >= pret) G = pret;
            else G = 0;
            sol[j] = max (sol[j - 1] - (v[j].timp - v[j - 1].timp) * cost + G, G - cost);
            maxim = max (sol[j], maxim);
        }
    }
    g << maxim << '\n';
}

int main () {
    citeste ();
    sort (v + 1, v + n + 1, conditie);
    rezolva ();
    return 0;
}