Cod sursa(job #1646748)

Utilizator cristina_borzaCristina Borza cristina_borza Data 10 martie 2016 17:32:57
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <algorithm>
#include <fstream>
#include <set>

#define NMAX 2005

using namespace std;

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

int n , c , sol;

pair <int , int> v[NMAX];

int solve(int price);

int main() {
    f >> n >> c;
    for(int i = 1 ; i <= n ; ++i) {
        f >> v[i].first >> v[i].second;
    }

    sort(v + 1 , v + n + 1);

    for(int i = 1 ; i <= n ; ++i) {
        sol = max(sol , solve(v[i].second));
    }
    g << sol;
    return 0;
}

int solve(int price) {
    int sol = 0 , sum = 0;
    for(int i = 1 ; i <= n ; ++i) {
        sum = sum - c * (v[i].first - v[i - 1].first);
        if(sum < 0)
            sum = 0;
        if(v[i].second >= price)
            sum = sum + price;
        sol = max(sol , sum - c);
    }

    return sol;
}