Pagini recente » Cod sursa (job #1235762) | Cod sursa (job #2465181) | Cod sursa (job #2048119) | Cod sursa (job #990539) | Cod sursa (job #3200913)
#include <fstream>
#include <queue>
#include <vector>
#include <cassert>
#include <algorithm>
#include <stack>
#define ll long long
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");
const int NMAX = 1e5;
int n, S, T;
int C[NMAX + 1];
int P[NMAX + 1];
deque<pair<int, int>> dq;
int dp[NMAX + 1];
ll answer;
int main()
{
cin >> n >> S >> T;
for(int i = 1; i <= n; i++)
cin >> C[i] >> P[i];
for(int i = 1; i <= n; i++)
{
if(!dq.empty() && i - dq.front().second > T)
dq.pop_front();
while(!dq.empty() && C[i] - i * S < dq.back().first)
dq.pop_back();
dq.push_back({C[i] - i * S, i});
dp[i] = dq.front().first;
}
for(int i = 1; i <= n; i++)
{
dp[i] += i * S;
answer += dp[i] * P[i];
}
cout << answer;
return 0;
}