Cod sursa(job #2719354)
| Utilizator | Data | 9 martie 2021 19:41:11 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.6 kb |
#include <fstream>
#include <deque>
using namespace std;
ifstream in("branza.in");
ofstream out("cost.out");
static int c[100002];
deque<int> dq;
int main() {
int n,t,s;
long long cost=0;
in>>n>>s>>t;
t++;
for(int i=0;i<n;i++) {
int p;
in >> c[i] >> p;
if (!dq.empty() && dq.front() == i - t) {
dq.pop_front();
}
while (!dq.empty() && c[i] <= c[dq.back()] + s * (i - dq.back()))
dq.pop_back();
dq.push_back(i);
cost += (long long) p*(c[dq.front()] + s * (i - dq.front()));
}
out<<cost;
return 0;
}
