Cod sursa(job #2306172)
Utilizator | Baras Nicholas Vladimir Laurentiu Vladi.Baras | Data | 21 decembrie 2018 18:26:53 |
---|---|---|---|
Problema | Branza | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.6 kb |
#include <bits/stdc++.h>
using namespace std;
const int NMAX=100000;
int v[NMAX+1],dq[NMAX+1];
int main()
{
int dr,st,n,s,t,i,kg,p,sum;
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d",&n,&s,&t);
sum=0,st=0,dr=-1;
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
scanf("%d",&p);
if(dq[st]==i-(t+1))
{
++st;
}
while(st<=dr&&v[i]<=(v[dq[dr]]+(i-dq[dr])*s))
{
--dr;
}
dq[++dr]=i;
sum+=p*(v[dq[st]]+(i-dq[st])*s);
}
printf("%d",sum);
return 0;
}