Pagini recente » Cod sursa (job #130564) | Rating Pop Radu (Radu_00) | Profil M@2Te4i | Monitorul de evaluare | Cod sursa (job #973367)
Cod sursa(job #973367)
//---------------------------------------------------------
#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
using namespace std;
//---------------------------------------------------------
const int NMax = 100100;
long long N, S, T, solution;
long long C[NMax], P[NMax];
void read(), solve(), write();
//---------------------------------------------------------
int main() {
#ifdef INFOARENA
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
#endif
read(); solve(); write();
}
//---------------------------------------------------------
void read() {
cin >> N >> S >> T;
for (int i = 1; i <= N; i++)
cin >> C[i] >> P[i];
}
//---------------------------------------------------------
struct minDeque {
deque<int> D;
inline void add(int position) {
for (; D.size() && C[D.back()] > C[position]; D.pop_back());
D.push_back(position);
}
inline void erase(int position) {
if (D.front() == position)
D.pop_front();
}
inline long long takeMin() {
return C[D.front()];
}
inline int takeMinPosition() {
return D.front();
}
} DQ;
void solve() {
C[0] = 1LL << 60;
for (int i = N; i >= 1; i--)
C[i] = C[i] + (N - i) * S;
for (int i = N; i >= N - T + 1; i--)
DQ.add(i);
for (int i = N; i >= 1; i--) {
int position = DQ.takeMinPosition();
solution += P[i] * (C[position] - S * (N - position) + S * (i - position));
DQ.add(max(i - T, 0LL));
DQ.erase(i);
}
}
//---------------------------------------------------------
void write() {
cout << solution << '\n';
}
//---------------------------------------------------------