Pagini recente » Cod sursa (job #1225783) | Cod sursa (job #3267546) | Cod sursa (job #1326984) | Cod sursa (job #583838) | Cod sursa (job #1098864)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <deque>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
const int Nmax = 100100;
const int oo = 0x3f3f3f3f;
long long N, T, S, C[Nmax], P[Nmax], sol;
deque <int> D;
int main()
{
fin >> N >> S >> T;
for(int i = 1; i <= N; i++)
fin >> C[i] >> P[i];
D.push_back(1); sol = C[1] * P[1];
for(int i = 2; i <= N; i++)
{
int poz = D.front();
sol += min(C[i] * P[i], C[poz] * P[i] + S * P[i] * (i - poz));
poz = D.back();
while(!D.empty() && C[poz] + S * (i - poz) >= C[i])
D.pop_back(), poz = D.back();
D.push_back(i);
if(D.front() <= i - T)
D.pop_front();
}
fout << sol;
return 0;
}