Pagini recente » Cod sursa (job #196598) | Cod sursa (job #2873153) | Cod sursa (job #2817762) | Cod sursa (job #1019483) | Cod sursa (job #2888593)
#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.begin();
deque<long long>::iterator it2 = deque2.begin();
mini = x * y;
while(it1 != deque1.end())
{
if(((*it1) * y + k * y * (i - (*it2))) < mini) mini = (*it1) * y + k * y * (i - (*it2));
*it2++;
*it1++;
}
s += mini;
deque1.push_back(x);
deque2.push_back(i);
}
}
out<<s;
return 0;
}