Cod sursa(job #1520882)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 9 noiembrie 2015 17:38:21
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#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; }