Cod sursa(job #2076332)

Utilizator ioana_marinescuMarinescu Ioana ioana_marinescu Data 26 noiembrie 2017 14:06:58
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
const int NMAX = 2005;
const int INF = 0x7fffffff;
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");

pair<int, int>v[NMAX];
int n, c;

int solve(int poz) {
    int sum=-1, sum_max=-INF, i, x=0;
    for(i=1; i<=n; i++) {
        if(v[i].second>=v[poz].second)
            x=v[poz].second;
        else x=0;
        if(i==1)
            sum=x-c;
        else
            sum=max(x-c, sum+x-c*(v[i].first-v[i-1].first));
        if(sum>sum_max)
            sum_max=sum;
    }
    return sum_max;
}
int main() {
    int i, maxim=-INF;
    fin>>n>>c;
    for(i=1; i<=n; i++)
        fin>>v[i].first>>v[i].second;
    sort(v+1, v+n+1);
    for(i=1; i<=n; i++)
        maxim=max(solve(i), maxim);
    fout<<maxim<<'\n';
    return 0;
}