Pagini recente » Cod sursa (job #559126) | Cod sursa (job #1745610) | Cod sursa (job #2670711) | Cod sursa (job #1051994) | Cod sursa (job #2888598)
#include <iostream>
#include <fstream>
#include <cmath>
#include <deque>
using namespace std;
int k;
long long n, t, x, y, i, s, mini;
deque <long long> deque1, deque2;
int main()
{
ifstream in("branza.in");
ofstream out("branza.out");
in>>n>>k>>t;
for(i = 1; i <= n; i++)
{
in>>x>>y;
while(i - deque2.front() > t && deque1.size() != 0)
{
deque1.pop_front();
deque2.pop_front();
}
if(deque1.size() == 0)
{
s += x * y;
deque1.push_back(x);
deque2.push_back(i);
}
else{
deque<long long>::iterator it1 = deque1.end();
deque<long long>::iterator it2 = deque2.end();
*it1--;
*it2--;
mini = x * y;
int ok = 1;
while(it1 != deque1.begin() && ok == 1)
{
if(((*it1) * y + k * y * (i - (*it2))) < mini){ mini = (*it1) * y + k * y * (i - (*it2)); ok = 0;}
*it2--;
*it1--;
}
if(((*it1) * y + k * y * (i - (*it2))) < mini && ok == 1) mini = (*it1) * y + k * y * (i - (*it2));
s += mini;
deque1.push_back(x);
deque2.push_back(i);
}
}
out<<s;
return 0;
}