Cod sursa(job #2156812)
| Utilizator | Data | 9 martie 2018 00:23:17 | |
|---|---|---|---|
| Problema | Branza | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.49 kb |
#include <fstream>
using namespace std;
#define ll long long
ifstream in("branza.in");
ofstream out("branza.out");
int a[5000001];
int d[5000001];
int main(){
int n,k,p,st=0,dr=-1,i,j;
in>>n>>p>>k;
ll s=0,c;
for(i=1; i<=n; ++i){
in>>a[i]>>c;
if(st<=dr && d[st]==i-k)
++st;
while(st<=dr && a[i]<=a[d[dr]]+(i-d[dr])*p)
--dr;
d[++dr]=i;
s+=(a[d[st]]+(i-d[st])*p)*c;
}
out<<s;
return 0;
}
