Pagini recente » Monitorul de evaluare | Cod sursa (job #1773544) | Cod sursa (job #406044) | Cod sursa (job #427640) | Cod sursa (job #3123984)
#include <bits/stdc++.h>
std :: vector <long long int> cost;
std :: deque <int> dq;
unsigned long long int ans;
int n, s, t, p, c, i, j;
int main() {
std :: ios_base :: sync_with_stdio(0);
dq.push_back(0);
cost.emplace_back(-1e9);
std :: ifstream fin("branza.in");
fin >> n >> s >> t >> c >> p;
cost.emplace_back(c);
ans += p * c;
dq.push_back(1);
for (i = 2; i <= t and i <= n; ++ i) {
fin >> c >> p;
cost.emplace_back(c);
while (cost[dq.back()] + (i - dq.back()) * s >= cost[i])
dq.pop_back();
dq.push_back(i);
ans += p * (cost[dq[1]] + (i - dq[1]) * s);
}
for (; i <= n; ++ i) {
fin >> c >> p;
if (i - dq[1] == t) {
dq.pop_front();
dq.front() = 0;
}
cost.emplace_back(c);
while (cost[dq.back()] + (i - dq.back()) * s >= cost[i])
dq.pop_back();
dq.push_back(i);
ans += p * (cost[dq[1]] + (i - dq[1]) * s);
}
fin.close();
std :: ofstream fout("branza.out");
fout << ans;
fout.close();
return 0;
}