Cod sursa(job #1725525)

Utilizator alittlezzCazaciuc Valentin alittlezz Data 5 iulie 2016 20:18:31
Problema Carnati Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <stdio.h>
#include <algorithm>
using namespace std;

pair <int, int> p[2005];

int main(){
    freopen("carnati.in", "r", stdin);
    freopen("carnati.out", "w", stdout);
    int n,i,j,sum,bst,C,id;
    bst = -2e9;
    scanf("%d %d",&n,&C);
    for(i = 1;i <= n;i++){
        scanf("%d %d",&p[i].first, &p[i].second);
    }
    sort(p+1, p+n+1);
    for(i = 1;i <= n;i++){
        int P = p[i].second;
        sum = 0;
        id = 1;
        for(j = 1;j <= n;j++){
            if(p[j].second >= P){
                sum += P;
            }
            //bst = max(bst, sum-C*(p[j].first-p[id].first+1));
            if(sum-C*(p[j].first-p[id].first+1) < 0){
                sum = 0;
                id = j+1;
            }
            bst = max(bst, sum-C*(p[j].first-p[id].first+1));
        }
    }
    printf("%d",bst);
    return 0;
}