Cod sursa(job #920356)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 20 martie 2013 11:08:51
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <algorithm>
#define maxim(a,b) (a>b)?a:b
using namespace std;

struct carnat {
    int t,p;
};
carnat v[2005];
int s[2005];
int n,c,summax;
bool cmp(carnat a,carnat b) {
    return (a.t < b.t);
}

int maximcurent(int pret) {
    int pmax=0,profit=0,precedent=-1,p1,p2;
    for (int i=0;i<=n;i++) if (v[i].p >= pret) {
        p1 = pret - c;
        p2 = profit - (v[i].t - precedent)*c + pret;
        p1 = maxim(p1,p2);
        profit = p1;
        pmax = maxim(pmax,p1);
        precedent = v[i].t;
    }
    return pmax;
}

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);
    for (int i=1;i<=n;i++) s[i] = s[i-1] + v[i].p;
    for (int i=0;i<=n;i++) {
        int x = maximcurent(v[i].p);
        summax = maxim(summax,x);
    }
    printf("%d",summax);
    return 0;
}