Cod sursa(job #209692)

Utilizator plastikDan George Filimon plastik Data 24 septembrie 2008 09:33:41
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 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], M[NMAX], Used[NMAX];
long long S[NMAX], Ans[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 = 0; i < n; ++ i)
		printf("%d ", S[i]);
	printf("\n");
	for (i = 0; i < n; ++ i)
		printf("%d\n", S[M[i]]);
	printf("\n");*/

	Ans[k - 1] = S[k - 1];
	Used[k - 1] = 0;
	for (i = k; i < n; ++ i) {
		Ans[i] = S[i] - S[M[i - k]];
		//printf("%lld %d\n", Ans[i], M[i - k]);
		Used[i] = M[i - k] + 1;
	}

	int end = k, start = 1;
	long long ans = - (1 << 63);
	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 %lld\n", start, end, ans);

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

	return 0;
}