Cod sursa(job #1336390)

Utilizator acomAndrei Comaneci acom Data 7 februarie 2015 17:39:24
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<fstream>
using namespace std;
#define NMAX 100005
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,p,u,C[NMAX],P[NMAX],D[NMAX];
long long sol;
int main()
{
    int i;
    fin>>n>>s>>t;
    for (i=1;i<=n;++i)
    {
        fin>>C[i]>>P[i];
        C[i]-=s*(i-1);
    }
    p=1, u=0;
    for (i=1;i<=n;++i)
    {
        while (p<=u && C[i]<C[D[u]])
            --u;
        D[++u]=i;
        sol+=(C[D[p]]+s*(i-1))*P[i];
        if (i-D[p]>=t-1) ++p;
    }
    fout<<sol<<"\n";
    return 0;
}