Cod sursa(job #2152316)
| Utilizator | Data | 5 martie 2018 13:51:13 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.54 kb |
#include <bits/stdc++.h>
using namespace std;
FILE*f=fopen("branza.in","r");
ofstream fout("branza.out");
int v[100005],dq[100005];
int main()
{
int n,s,t,st=1,dr=0,cant,pret,sum=0;
int i=1;
fscanf(f,"%d%d%d",&n,&s,&t);
while(i<=n)
{
fscanf(f,"%d%d",&v[i],&pret);
while(st<=dr&&(v[i]-s*(i-dq[dr]))<=v[dq[dr]])
dr--;
dq[++dr]=i;
if(dq[st]==i-t)
st++;
sum=sum+pret*(v[dq[st]]+s*(i-dq[st]));
i++;
}
fout<<sum;
return 0;
}
