Pagini recente » Monitorul de evaluare | Cod sursa (job #1065743) | Istoria paginii utilizator/cricricri00 | Monitorul de evaluare | Cod sursa (job #2057705)
#include <stdio.h>
#define MAX_N 100000
namespace My
{
template< class T >
class deque
{
public:
deque() {m_left = 0, m_right = -1;}
T peak_front(){ return m_deque[m_left]; }
T peak_back(){ return m_deque[m_right]; }
void pop_front() {m_left++;}
void push_back(T val) {m_deque[++m_right] = val;}
void pop_back() {m_right--;}
bool is_empty() {return m_left > m_right;}
private:
T m_deque[MAX_N];
int m_left, m_right;
};
};
struct elem
{
int pos, val;
elem() {}
elem(int _pos, int _val): pos(_pos), val(_val) {}
};
My::deque<elem> deque;
int main()
{
FILE *fin = fopen("branza.in", "r"),
*fout = fopen("branza.out", "w");
int n, s, t;
long long sum;
fscanf(fin, "%d %d %d", &n, &s, &t);
sum = 0;
for(int i = 0; i < n; i++)
{
int c, q;
fscanf(fin, "%d %d", &c, &q);
if(!deque.is_empty() && deque.peak_front().pos == i - t)
deque.pop_front();
while ( !deque.is_empty() &&
c <= deque.peak_back().val + s * (i - deque.peak_back().pos)
)
deque.pop_back();
deque.push_back(elem(i, c));
sum += (deque.peak_front().val + s * (i - deque.peak_front().pos)) * q;
}
fprintf(fout, "%lld", sum);
fclose(fin);
fclose(fout);
return 0;
}