Cod sursa(job #2058222)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 5 noiembrie 2017 12:24:57
Problema Carnati Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>

using namespace std;

FILE *in,*out;

const int nmax = 2000;

struct Persoana
{
    int t,p;
    bool operator< (Persoana other) const
    {
        if(t != other.t)
            return t < other.t;
        else
            return p < other.p;
    }
}v[1+nmax];

int main()
{
    in = fopen("carnati.in","r");
    out = fopen("carnati.out","w");
    int n,c;
    fscanf(in,"%d %d",&n,&c);
    for(int i = 1;i <= n;i ++)
        fscanf(in,"%d %d",&v[i].t,&v[i].p);
    sort(v+1,v+n+1);
    long long s = 0,maxim = -2000000001,tstart = 0;
    for(int i = 1;i <= n;i ++)
    {
        s = 0;
        tstart = 0;
        for(int j = 1;j <= n;j ++)
        {
            if(s <= 0 && v[j].t > tstart)
            {
                s = 0;
                tstart = v[j].t;
            }
            if(v[j].p >= v[i].p)
                s += 1LL*v[i].p;
            s -= ( 1LL*c*(v[j].t+1 - tstart));
            tstart = v[j].t+1;
            if(s > maxim)
                maxim = s;
        }
    }
    fprintf(out,"%lld",maxim);
    return 0;
}