Cod sursa(job #1046677)

Utilizator tudorv96Tudor Varan tudorv96 Data 3 decembrie 2013 12:32:08
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
#include <deque>
using namespace std;

ifstream fin ("secv2.in");
ofstream fout ("secv2.out");

const int N = 5e4 + 5;

int v[N], sp[N], n, k;
deque <int> d;

int main() {
	fin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		fin >> v[i];
		sp[i] = sp[i-1] + v[i];
	}
	fin.close();
	int x = 1, y = k;
	for (int i = 1; i <= k; ++i)
		d.push_front(i);
	int MAX = sp[k];
	for (int i = k + 1; i <= n; ++i) {
		while (sp[i] > sp[d.back()] && d.size() >= (unsigned)k)
			d.pop_back();
		d.push_back(i);
		if (sp[d.back()] - sp[d.front()-1] > MAX) {
			MAX = sp[d.back()] - sp[d.front()-1];
			x = d.front();
			y = d.back();
		}
	}
	fout << x << " " << y << " " << MAX;		
}