Pagini recente » Cod sursa (job #2186978) | Cod sursa (job #2096237)
#include <bits/stdc++.h>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
const int NMAX = 1e5;
int n, t, s;
int c[NMAX + 2], p[NMAX + 2];
deque<int> dq;
long long ans;
long long sapt[NMAX + 2];
int main()
{
in >> n >> s >> t;
for(int i = 1; i <= n; i++)
{
in >> c[i] >> p[i];
while(!dq.empty() && dq.front() < i - t)
dq.pop_front();
while(!dq.empty() && c[dq.back()] + s * (n - dq.back()) >= c[i] + s * (n - i))
dq.pop_back();
dq.push_back(i);
sapt[i] = c[dq.front()] + s * (n - dq.front()) - s * (n - i);
}
for(int i = 1; i <= n; i++)
ans += 1LL * p[i] * sapt[i];
out << ans << '\n';
return 0;
}