Cod sursa(job #2207885)
Utilizator | Data | 27 mai 2018 10:42:02 | |
---|---|---|---|
Problema | Branza | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.45 kb |
#include <fstream>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long s,T,S,n,v[100001],c[100001],dq[100001];
int i,p,u;
int main()
{ f>>n>>S>>T;
p=0;u=-1;
for(i=1;i<=n;i++){
f>>v[i]>>c[i];
while(u>=p&&v[i]<=v[dq[u]]+(i-dq[u])*S)
u--;
dq[++u]=i;
if(i-dq[p]>T)
p++;
s=s+v[dq[p]]*c[i]+S*(i-dq[p])*c[i];
}
g<<s;
return 0;
}