Cod sursa(job #2389540)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 27 martie 2019 11:08:06
Problema Carnati Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <algorithm>
#define t first
#define p second
#define INF 1000000000

using namespace std;

ifstream fin("carnati.in");
ofstream fout("carnati.out");

long long n,c,i,j,x,g,maxim,s;
pair<int, int> v[2005];

int main()
{
    fin >> n >> c;
    for (i=1; i<=n; i++)
        fin >> v[i].t >> v[i].p;
    sort(v+1, v+n+1);
    ///pretul fixat va fi unul din cele ale cumparatorilor
    ///a[i] = profitul maxim daca magazinul este deschis cand trece i
    ///sortam clientii dupa timpul la care trec si facem subsecventa de suma maxima
    for (i=1; i<=n; i++)
    {
        x = v[i].p;
        s = 0;
        for (j=1; j<=n; j++)
        {
            if (x <= v[j].p)
                g = x;
            else
                g = 0;
            long long a = -(v[j].t-v[j-1].t)*1LL*c+g;
            long long b = g-c;
            if (s+a >= b)
                s += a;
            else
                s = b;
            maxim = max(maxim, s);
        }
    }
    fout << maxim;
    return 0;
}