Cod sursa(job #904363)

Utilizator misinozzz zzz misino Data 4 martie 2013 11:14:47
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.46 kb
#include<fstream>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long n,s,t,i,sol,p,u,a[100010],b[100010],v[100010];
int main()
{
    f>>n>>s>>t;
    p=1;
    u=0;
    for(i=1;i<=n;++i)
    {
        f>>a[i]>>b[i];
        while(v[p]+t<i)
        ++p;
        while(p<=u&&a[i]<=(a[v[u]]+(i-v[u])*s))
        --u;
        ++u;
        v[u]=i;
        sol+=b[i]*(a[v[p]]+(i-v[p])*s);
    }
    g<<sol<<'\n';
    return 0;
}