Cod sursa(job #2310182)

Utilizator TeodoraMiuTeodora Miu TeodoraMiu Data 30 decembrie 2018 18:50:13
Problema Carnati Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
struct pret
{
    int t,p;
};
bool cmp(pret a,pret b){return a.t<b.t;}
int main()
{
    ifstream fin("carnati.in");
    ofstream fout("carnati.out");
    int n,c,i,pmax=-2000000000,G,news,old,j;
    pret v[2000];
    fin>>n>>c;
    for (i=0; i<n; i++)
        fin>>v[i].t>>v[i].p;
    sort(v,v+n,cmp);
    for(i=0; i<n; i++)
    {
        int ans=-2000000000,sum=0;
        for(int j=0;j<n;j++){
            sum=max(sum-(v[j].t-((j==0)?0:(v[j-1].t)))*c,0);
            if(v[i].p<=v[j].p)
                sum+=v[i].p;
            ans=max(ans,sum-c);
        }
        if(pmax<ans)
            pmax=ans;
        /*
        oldMax=0;
        //news=p[i]-c;
        //if(news>pmax)
        //    pmax=news;
        //old=news;
        for(j=0;j<n;j++)
        {
            if(v[j].p>=v[i].p)
                G=v[i].p;
            else
                G=0;
            newMax=oldMax-(v[j].t-((j==0)?0:(v[j-1].t)))*c;
            if(newMax>=0)
                newMax+=G;
            else
                newMax=G;
            //if(news<G-c) news=G-c;
            if(newMax>pmax)
                pmax=newMax;
            old=news;
        }*/

    }
    fout<<pmax;
    fin.close();
    fout.close();
    return 0;
}