Cod sursa(job #2058225)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 5 noiembrie 2017 12:30:07
Problema Carnati Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 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];

long long max(long long a,long long b)
{
    if(a > b)
        return a;
    return b;
}

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,x;
    for(int i = 1;i <= n;i ++)
    {
        s = 0;
        for(int j = 1;j <= n;j ++)
        {
            if(v[j].p >= v[i].p)
                x = v[i].p;
            else
                x = 0;
            if(j == 1)
                s = x-c;
            else
                s = max(s + x - c*(v[j].t - v[j-1].t), x-c);
            if(s > maxim)
                maxim = s;
        }
    }
    fprintf(out,"%lld",maxim);
    return 0;
}