Cod sursa(job #1751076)
| Utilizator | Data | 31 august 2016 18:08:34 | |
|---|---|---|---|
| Problema | Branza | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.61 kb |
#include <stdio.h>
#include <deque>
#include <climits>
#define maxn 100010
using namespace std;
int nums[maxn], n, s, t, q;
long long sol = 0;
deque<int> D;
int main() {
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
scanf("%d %d %d", &n, &s, &t);
for (int i = 1; i <= n; i ++) {
scanf("%d %d", &nums[i], &q);
while (!D.empty() && (i - D.back() > t || nums[i] <= nums[D.back()] + s * (i - D.back())))
D.pop_back();
D.push_back(i);
if (i - D.front() > t)
D.pop_front();
sol += 1LL * (nums[D.front()] + (i - D.front()) * s) * q;
}
printf("%lli\n", sol);
return 0;
}
