Cod sursa(job #1046715)

Utilizator tudorv96Tudor Varan tudorv96 Data 3 decembrie 2013 13:23:10
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 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, MAX = sp[k];
	for (int i = k; i <= n; ++i) {
		while (d.size() && sp[d.back()] > sp[i - k])
			d.pop_back();
		d.push_back (i - k);
		if (MAX < sp[i] - sp[d.front()]) {
			MAX = sp[i] - sp[d.front()];
			x = d.front() + 1;
			y = i;
		}
	}
	fout << x << " " << y << " " << MAX;		
}