Cod sursa(job #2413730)

Utilizator BAlexandruBorgovan Alexandru BAlexandru Data 23 aprilie 2019 17:46:39
Problema Carnati Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("carnati.in");
ofstream g("carnati.out");

int n, c, last, i, w ;
int t[2005], p[2005], ind[2005];
long long s, maxim, care;

bool cmp(int a, int b)
{
    return t[a] < t[b];
}

int main()
 {
    f >> n >> c;
    for (i = 1; i <= n; i++)
        f >> t[i] >> p[i], ind[i] = i;
    sort(ind+1,ind+n+1,cmp);
    for(i=1;i<=n;i++)
        g<<t[i]<<" "<<p[i]<<"\n";
    t[0] = -1;
    for (w = 1; w <= n; w++)
        {
        last = 0;
        s = 0;
        for (i = 1; i <= n; i++)
        {
            if (p[ind[i]] >= p[w])
            {
                if (s+p[w]-c*(t[ind[i]]-t[ind[last]]) >= p[w]-c)
                 s += p[w]-c*(t[ind[i]]-t[ind[last]]);
                else
                 s = p[w]-c;
                if (s > maxim)
                    maxim = s;
                last = i;
            }
        }
    }
    g << maxim;
}