Pagini recente » Cod sursa (job #1690504) | Cod sursa (job #2898224) | Cod sursa (job #349406) | Cod sursa (job #2960514) | Cod sursa (job #2268691)
#include <iostream>
#include <deque>
#include <vector>
#include <queue>
#include <cstdio>
#include <climits>
using namespace std;
long long n,t,s;
long long rez;
struct branza
{
long long pret;
int c, poz;
}b;
struct Deque
{
branza q[100005];
int st = 0, dr = 0;
void pop_back()
{
--dr;
}
void pop_front()
{
++st;
}
void push_back(branza x)
{
q[dr++]=x;
}
bool empty()
{
return st==dr;
}
branza back()
{
return q[dr-1];
}
branza front()
{
return q[st];
}
}q;
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
scanf("%d %d %d\n", &n, &s, &t);
for(int i=0;i<n;++i)
{
scanf("%lld %d\n", &b.pret, &b.c);
b.poz = i;
while(!q.empty() && q.back().pret+s*(i-q.back().poz)>b.pret)
q.pop_back();
q.push_back(b);
rez+=(q.front().pret+s*(i-q.front().poz))*b.c;
if(i-q.front().poz>=t)
q.pop_front();
}
cout<<rez;
return 0;
}