Cod sursa(job #1941627)

Utilizator adriannicolaeAdrian Nicolae adriannicolae Data 27 martie 2017 15:16:02
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>

#define maxN 2000

using namespace std;

int N, C;
struct client{
    int T, P;
}v[maxN + 1];

inline bool cmp(client A, client B){
    if (A.T == B.T)
        return A.P < B.P;
    return A.T < B.T;
}

inline int maximum(int a, int b){ return (a > b ? a : b);}

int totalPrice(int P){
    int maxs, s;
    maxs=s=0;
    for (int i = 1 ; i <= N; i++){
        s=maximum(s-(v[i].T-v[i-1].T)*C, 0);
        if (P<=v[i].P)
            s+=P;
        maxs=maximum(maxs, s-C);
    }
    return maxs;
}

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++)
        ans=maximum(ans, totalPrice(v[i].P));
    
    printf("%d\n", ans);
    
    return 0;
}