Pagini recente » Cod sursa (job #2010992) | Cod sursa (job #1006814) | Rating Mircea Milencianu (Mircea11) | Monitorul de evaluare | Cod sursa (job #1520882)
#include <fstream>
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
class deque_by_vector{
vector<long long>& vals;
deque<int> dq;
public:
deque_by_vector(vector<long long>& v): vals(v){}
void push(const int x){
while(!dq.empty() && vals[dq.back()] > vals[x]){
dq.pop_back(); }
dq.push_back(x); }
void pop(const int x){
if(!dq.empty() && dq.front() == x){
dq.pop_front(); } }
int front(){
return dq.front(); } };
int main(){
ifstream f("branza.in");
ofstream g("branza.out");
int n, s, t;
f >> n >> s >> t;
long long rez = 0;
vector<long long> valori_asociate(n, 0);
deque_by_vector dq(valori_asociate);
long long delta = -s, c, p;
for(int i = 0; i < n; ++i){
f >> c >> p;
dq.pop(i-t-1);
delta += s;
valori_asociate[i] = -delta+c;
dq.push(i);
rez += p * (valori_asociate[dq.front()] + delta); }
g << rez;
return 0; }