Cod sursa(job #1657596)

Utilizator Emy1337Micu Emerson Emy1337 Data 20 martie 2016 17:08:35
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("carnati.in");
ofstream fout("carnati.out");

const int MAXN=2e3+5;
int n,p,rez;
pair <int , int> v[MAXN];

int solve( int pret)
{
    int s=0,rez=0;

    for(int i=1; i<=n; i++)
    {
        if(s>0)
        {
            if(v[i].second>=pret)
                s+=pret;

            s-=p * ( v[i].first - v[i-1].first ) ;
        }
        else
        {
            if(v[i].second>=pret)
                s=pret;
        }

        rez=max(rez,s-p);
    }
    return rez;


}

int main()
{

    fin>>n>>p;
    for(int i=1; i<=n; i++)
        fin>>v[i].first>>v[i].second;

    sort(v+1,v+n+1);

    for(int i=1; i<=n; i++)
        rez=max(rez,solve(v[i].second));

    fout<<rez;



}