Cod sursa(job #2072168)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 21 noiembrie 2017 15:20:31
Problema Carnati Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 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,c,i,j,pret;
    long long maxi,sc;
    fscanf (fin,"%d%d",&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;
        //if (pret==115)
          //  printf ("a");
        sc=0;
        for (j=1;j<=n;j++){
            if (sc==0){
                if (profit (v[j].second-c,pret))
                    sc=pret-c;
            }
            else if (sc-(long long)(v[j].first-v[j-1].first)*c+profit (v[j].second,pret)>0)
                sc=sc-(long long)(v[j].first-v[j-1].first)*c+profit (v[j].second,pret);
            else {
                if (profit (v[j].second-c,pret))
                    sc=pret-c;
                else sc=0;
            }
            if (maxi<sc){
                maxi=sc;
                //printf ("%d ",pret);
            }
            //maxi=max(maxi,sc);
        }
    }
    fprintf (fout,"%lld",maxi);
    return 0;
}