Cod sursa(job #2072213)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 21 noiembrie 2017 16:16:50
Problema Carnati Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <cstdio>
#include <algorithm>

using namespace std;
pair <int,int> v[2001];
int profit (int x,int pret){
    if (x<pret)
        return 0;
    else return pret;
}
int main()
{
    FILE *fin=fopen ("carnati.in","r");
    FILE *fout=fopen ("carnati.out","w");
    int n,i,j,pret;
    long long maxi,sc,c;
    fscanf (fin,"%d%lld",&n,&c);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d%d",&v[i].first,&v[i].second);
    sort (v+1,v+n+1);
    maxi=0;
    for (i=1;i<=n;i++){
        pret=v[i].second;
        sc=0;
        for (j=1;j<=n;j++){
            if (sc==0){
                if (profit (v[j].second,pret) && pret-c>0)
                    sc=pret-c;
            }
            else if (sc-(v[j].first-v[j-1].first)*c+profit (v[j].second,pret) > max(profit (v[j].second,pret)-c,1LL*0))
                sc=sc-(v[j].first-v[j-1].first)*c+profit (v[j].second,pret);
            else
                sc=max(profit (v[j].second,pret)-c,1LL*0);
            if (maxi<sc)
                maxi=sc;
            //maxi=max(maxi,sc);
        }
    }
    fprintf (fout,"%lld",maxi);
    return 0;
}