Pagini recente » agm-2018/runda1 | Diferente pentru preoni-2007/runda-finala/poze/deschidere intre reviziile 6 si 4 | Cod sursa (job #1235964) | Diferente pentru preoni-2007/runda-finala/poze/deschidere intre reviziile 6 si 3 | Cod sursa (job #1813092)
#include <iostream>
#include <cstdio>
#include <deque>
using namespace std;
struct branza
{
int c, p;
}sapt[100005];
int n, s, t;
long long costMinim, m[100005];
deque <int> q;
void citire()
{
scanf("%d%d%d", &n, &s, &t);
for(int i=1; i<=n; ++i)
scanf("%d%d", &sapt[i].c, &sapt[i].p);
}
void rezolvare()
{
for(int i=1; i<=n; ++i)
{
while(!q.empty())
q.pop_back();
q.push_front(sapt[i].c);
for(int j=max(1, i-t); j<=i; ++j)
{
while (!q.empty() && q.back()>sapt[j].c+(i-j)*s)
q.pop_back();
q.push_back(sapt[j].c+(i-j)*s);
}
costMinim+=sapt[i].p*q.front();
}
}
int main()
{
freopen("branza.in", "r", stdin);
freopen("branza.out", "w", stdout);
citire();
rezolvare();
printf("%lld", costMinim);
return 0;
}