Pagini recente » Cod sursa (job #1653944) | Cod sursa (job #2823331) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #252308)
Cod sursa(job #252308)
#include <cstdio>
#include <deque>
using namespace std;
#define MAX_N 100005
#define val first
#define poz second
long long P[MAX_N], C[MAX_N], M[MAX_N];
int N, S, T;
void citire()
{
scanf("%d %d %d",&N, &S, &T);
for(int i = 1; i <= N; ++i)
scanf("%lld %lld",P+i, C+i);
}
void solve()
{
deque <pair<long long, int> > Q;
for(int i = 1; i <= N; ++i)
{
long long x = (N - i)*S + P[i];
while(!Q.empty() && Q.back().val >= x) Q.pop_back();
while(!Q.empty() && Q.front().poz <= i-T) Q.pop_front();
Q.push_back(make_pair(x, i));
M[i] = Q.front().val - (N-i)*S;
}
long long Rez = 0;
for(int i = 1; i <= N; ++i)
Rez += M[i]*C[i];
printf("%lld\n",Rez);
}
int main()
{
freopen("branza.in","rt",stdin);
freopen("branza.out","wt",stdout);
citire();
solve();
}