Pagini recente » Cod sursa (job #38048) | Cod sursa (job #2154578) | Cod sursa (job #332383) | Cod sursa (job #2146660) | Cod sursa (job #1806638)
#include <iostream>
#include <cstdio>
#include <deque>
#include <algorithm>
#define N 100005
using namespace std;
int n, s, t;
long long suma;
struct zi
{
long long cost, cantitate;
}vec[N];
deque <int> dq;
void compara(int poz)
{
while(!dq.empty() && vec[dq.back()].cost + s * (poz - dq.back()) > vec[poz].cost)
{
dq.pop_back();
}
dq.push_back(poz);
if(poz - dq.front() > t)
{
dq.pop_front();
}
suma += (vec[dq.front()].cost + s * (poz - dq.front())) * vec[poz].cantitate;
}
void citire()
{
scanf("%d %d %d\n", &n, &s, &t);
scanf("%lld %lld\n", &vec[1].cost, &vec[1].cantitate);
dq.push_front(1);
suma = (vec[1].cost * vec[1].cantitate);
for(int i = 2 ; i <= n ; ++i)
{
scanf("%lld %lld\n", &vec[i].cost, &vec[i].cantitate);
compara(i);
}
printf("%lld",suma);
}
int main()
{
freopen("branza.in","r",stdin);
freopen("branza.out","w",stdout);
citire();
return 0;
}