Cod sursa(job #1770524)

Utilizator CrystyAngelDinu Cristian CrystyAngel Data 4 octombrie 2016 15:36:32
Problema Carnati Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

struct str
{
    int t,pret;
};

bool compare(str a,str b)
{
    return a.t<b.t;
}

str v[3000];
int n,c,i,s,mx,t1,a,b,k,p;

int main()
{
    fin>>n>>c;
    for(i=1; i<=n; ++i)
    {
        fin>>v[i].t>>v[i].pret;
    }
    sort(v+1,v+n+1,compare);
    mx=-1000000000;
    for(k=1; k<=n; ++k)
    {
        p=v[k].pret;
        s=0;
        t1=v[1].t;
        for(i=1; i<=n; ++i)
        {
            s-=c*(v[i].t-t1+1);
            if(p<=v[i].pret)
                s+=p;
            if(s<0)
            {
                s=0;
                t1=v[i+1].t;
            }
            else
            t1=v[i].t+1;


            mx=max(mx,s);
        }
    }
    fout<<mx;
}