Cod sursa(job #1777803)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 12 octombrie 2016 21:41:10
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <algorithm>
#define lim 2005
using namespace std;
struct elem{int t,p;};
elem v[lim];
bool cmp(elem a,elem b){return a.t<b.t;}
long long max(long long a,long long b){
    if(a>b)
        return a;
    return b;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("carnati.in","r");
    fout=fopen("carnati.out","w");
    int i,j,n;
    long long rasp=-2000000000,sum,c,plata,continua;
    fscanf(fin,"%d%lld",&n,&c);
    v[0].t=-1500;
    for(i=1;i<=n;i++)
        fscanf(fin,"%d%d",&v[i].t,&v[i].p);
    sort(v+1,v+n+1,cmp);
    for(i=1;i<=n;i++){
        sum=0;
        for(j=1;j<=n;j++){
            plata=(long long)(v[j].t-v[j-1].t)*c;
            if(v[i].p<=v[j].p){
                continua=sum+(long long)v[i].p-plata;
                sum=max(continua,v[i].p-c);
            }
            else{
                continua=sum-plata;
                sum=max(continua,-c);
            }
            if(sum>rasp)
                rasp=sum;
        }
    }
    fprintf(fout,"%lld",rasp);
    fclose(fin);
    fclose(fout);
    return 0;
}