Cod sursa(job #1614101)

Utilizator Matei_IgnutaMatei Ignuta Matei_Ignuta Data 25 februarie 2016 20:00:47
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX 2001

struct client {int t, p;};

client v[MAX];

int n, c;
int profit(int x){
    int ans = 0, vf = 0, last = v[1].t - 1;
    for(int i=1; i<=n; i++){
        vf = vf - (v[i].t - last - 1)*c;
        last = v[i].t - 1;
        if(vf<0)
            vf = 0;
        if(v[i].p>=x)
            vf = vf + x;
        vf = vf - c;
        last = v[i].t;
        if(vf>ans)
            ans = vf;
    }
    return ans;
}

bool cmp (client a, client b){
    return a.t < b.t;
    }

int main(){
    freopen ("carnati.in", "r", stdin);
    freopen ("carnati.out", "w", stdout);
    scanf ("%d %d", &n, &c);
    for(int i=1; i<=n; i++)
        scanf("%d%d", &v[i].t, &v[i].p);
    sort(v+1, v+n+1, cmp);
    int ans = 0;
    for(int i=1; i<=n; i++){
        if(profit(v[i].p)>ans)
            ans = profit(v[i].p);
    }
    printf("%d", ans);
    return 0;
}