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