Cod sursa(job #1454590)

Utilizator GilgodRobert B Gilgod Data 27 iunie 2015 00:09:33
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <assert.h>

const char IN[] = "secv2.in", OUT[] = "secv2.out";
const int NMAX = 50001;
const int INF = 0x3f3f3f3f;

using namespace std;

int N, K;
int V[NMAX];
int best[NMAX];
int st[NMAX];

inline void read_data() {
	assert(freopen(IN, "r", stdin));
	assert(scanf("%d %d", &N, &K));
	for (int i = 0; i < N; ++i)
		assert(scanf("%d", &V[i]));
	fclose(stdin);
}

inline void PD() {
	int bestMax = 0, start = 0, end = K-1;
	for (int i = 0; i < K; ++i) bestMax += V[i];
	best[0] = V[0];
	st[0] = 0;
	for (int i = 1; i < N; ++i) {
		best[i] = V[i];
		st[i] = i;
		if (best[i] + best[i - 1] > best[i]) {
			best[i] += best[i - 1];
			st[i] = st[i - 1];
			if (i - st[i] + 1 >= K) {
				if (best[i] > bestMax) {
					bestMax = best[i];
					end = i;
					start = st[i];
				}
			}
		}
	}
	fprintf(fopen(OUT, "w"), "%d %d %d\n", start+1, end+1, bestMax);
}

int main() {
	read_data();
	PD();
	return 0;
}