Pagini recente » Cod sursa (job #2297231) | Cod sursa (job #1931430) | Cod sursa (job #895929) | Cod sursa (job #546988) | Cod sursa (job #357550)
Cod sursa(job #357550)
#include <cstdio>
#include <algorithm>
#include <deque>
using namespace std;
#define FIN "branza.in"
#define FOUT "branza.out"
#define N 100007
int n, s, t;
unsigned long long c;
pair <int,int> v[N];
deque <int> q;
void read()
{
int i;
freopen(FIN,"r",stdin);
scanf("%d %d %d", &n, &s, &t);
for (i = 1; i <= n; ++ i)
scanf("%d %d", &v[i].first, &v[i].second);
}
inline unsigned long long cost(int i,int j)
{
return v[i].first + s * (j - i);
}
void solve()
{
int i;
for (i = 1; i <= n; ++ i)
{
if(!q.empty() && q.front() < i - t)
q.pop_front();
while(!q.empty() && cost(q.back(),i) >= v[i].first)
q.pop_back();
q.push_back(i);
c += cost(q.front(), i) * v[i].second;
}
}
void write()
{
freopen(FOUT,"w",stdout);
printf("%llu\n", c);
}
int main()
{
read();
solve();
write();
}