Cod sursa(job #2889597)
| Utilizator | Data | 12 aprilie 2022 23:13:07 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.62 kb |
#include <iostream>
#include <fstream>
#define LEN 100005
using namespace std;
ifstream fin ("branza.in");
ofstream fout ("branza.out");
long long N, S, T, st, dr, sol;
long long c[LEN], p[LEN], d[LEN];
int main (){
fin>>N>>S>>T;
for(int i=1; i<=N; i++)
fin>>c[i]>>p[i];
d[1]=1, st=1, dr=1;
sol+=c[1]*p[1];
for(int i=2; i<=N; i++){
while(st <= dr && c[i] <= c[d[dr]] + S*(i-d[dr]))
dr--;
d[++dr]=i;
if(i-d[st] == T+1) st++;
sol+=(c[d[st]] + S*(i-d[st])) * p[i];
}
fout<<sol;
return 0;
}
