Cod sursa(job #1127118)

Utilizator jumper007Raul Butuc jumper007 Data 27 februarie 2014 11:14:05
Problema Deque Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

vector<int> nr;
deque<int> deQueue;

void readData(int &, int &);
void solve(int, int, long long &);
void writeData(long long);

int main(int argc, char *argv[]) {
	int totalSize, subseqSize;
	long long sum;
	
	readData(totalSize, subseqSize);
	solve(totalSize, subseqSize, sum);
	writeData(sum);

	return 0;
}

void readData(int &totalSize, int &subseqSize) {
	fstream in("deque.in", ios::in);
	in >> totalSize >> subseqSize;
	nr.resize(totalSize);
	for (int i = 1; i <= totalSize; ++i) {
		nr.push_back(i);
	}
	in.close();
}

void solve(int totalSize, int subseqSize, long long &sum) {
	for (vector<int>::iterator it = nr.begin(); it != nr.end(); ++it) {
		while (!deQueue.empty() && (*it) < deQueue.back()) {
			deQueue.pop_back();
		}
		
		deQueue.push_back(*it);
		
		if (deQueue.front() == (*it) - subseqSize) {
			deQueue.pop_front();
		}

		if ((*it) >= subseqSize) {
			sum += deQueue.front();
		}
	}
}

void writeData(long long sum) {
	fstream out("deque.out", ios::out);
	out << sum;
	out.close();
}