Cod sursa(job #1984058)
Utilizator | Data | 23 mai 2017 16:09:18 | |
---|---|---|---|
Problema | Branza | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.56 kb |
#include <iostream>
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
long long n,s,t,a[100001],d[100001],st=1,dr=0,c;
void stanga(int i)
{
if(d[st]<i-t)
++st;
}
void dreapta(int i)
{
while(st <= dr && s*(i-d[dr])+a[d[dr]]>=a[i])
dr--;
d[++dr]=i;
}
int main()
{
long long i,S=0;
in>>n>>s>>t;
for(i=1; i<=n; i++)
{
in>>a[i]>>c;
dreapta(i);
stanga(i);
S=S+c*(s*(i-d[st])+a[d[st]]);
}
out<<S;
return 0;
}