Pagini recente » Cod sursa (job #2310720) | Cod sursa (job #2881047) | Cod sursa (job #458882) | Cod sursa (job #691688) | Cod sursa (job #2728650)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
struct branza
{
long long C, P;
};
int back = 0, front = 1;
int deque[100001];
branza v[100001];
void push_back(int x)
{
++back;
deque[back] = x;
}
void pop_front()
{
++front;
}
void pop_back()
{
--back;
}
int get_front()
{
return deque[front];
}
int get_back()
{
return deque[back];
}
bool is_Empty()
{
return (front > back);
}
int main()
{
long long N, T;
int S;
long long cost_total = 0;
fin >> N >> S >> T;
for(int i=0; i<N; ++i)
{
fin >> v[i].C >> v[i].P;
}
for(int i=0; i<N; ++i)
{
while(!is_Empty() && (i-get_front()) > T)
pop_front();
while(!is_Empty() && v[i].C < v[get_back()].C + S*(i-get_back()))
pop_back();
push_back(i);
cost_total += v[i].P * (v[get_front()].C + S*(i-get_front()));
}
fout << cost_total;
return 0;
}