Cod sursa(job #209689)

Utilizator plastikDan George Filimon plastik Data 24 septembrie 2008 09:07:21
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
// http://infoarena.ro/problema/secv2
#define _CRT_SECURE_NO_DEPRECATE

#include <cstdio>
#include <deque>
using namespace std;

//deque<int> M;

const int NMAX = 50001;
int A[NMAX], S[NMAX], M[NMAX];
int Ans[NMAX], Used[NMAX];

int main() {

	freopen("secv2.in", "r", stdin);
	freopen("secv2.out", "w", stdout);

	int n, k;
	scanf("%d %d", &n, &k);
	int i;
	for (i = 0; i < n; ++ i) {
		scanf("%d", &A[i]);
		if (i == 0) {
			S[i] = A[i];
			M[i] = 0;
		} else {
			S[i] = S[i - 1] + A[i];
			if (S[M[i - 1]] < S[i])
				M[i] = M[i - 1];
			else
				M[i] = i;
		}
	}

	for (i = k - 1; i < n; ++ i) {
		Ans[i] = S[i];
		if (i >= k) {
			Ans[i] -= S[M[i - k]];
			Used[i] = M[i - k] + 1;
		}
	}

	int ans = 0, end = k, start = 1;
	for (i = k - 1; i < n; ++ i) {
		if (Ans[i] > ans) {
			end = i + 1;
			ans = Ans[i];
			start = Used[i] + 1;
		}
		//printf("%d ", A[i]);
	}

	printf("%d %d %d\n", start, end, ans);

	/*for (i = 0; i < n; ++ i)
		printf("%d ", S[i]);
	printf("\n");*/

	return 0;
}