Pagini recente » Cod sursa (job #2128506) | Cod sursa (job #2332407) | Cod sursa (job #716758) | Cod sursa (job #2915778) | Cod sursa (job #2888760)
#include <iostream>
#include <fstream>
#include <cmath>
#include <deque>
using namespace std;
int k, ok;
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();
mini = x * y;
*it1--;
*it2--;
ok = 0;
while(it1 != deque1.begin() && ok == 0)
{
if(((*it1) * y + k * y * (i - (*it2))) < mini)
{
mini = (*it1) * y + k * y * (i - (*it2));
ok = 1;
}
*it2--;
*it1--;
}
if((((*it1) * y + k * y * (i - (*it2))) < mini) && ok == 0)mini = (*it1) * y + k * y * (i - (*it2));
s += mini;
deque1.push_back(x);
deque2.push_back(i);
}
}
out<<s;
return 0;
}