Cod sursa(job #2274024)

Utilizator memecoinMeme Coin memecoin Data 1 noiembrie 2018 11:11:23
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
 
using namespace std;

#define MAXN 50005

int n, k;

int a[MAXN];
int s[MAXN];
int best[MAXN];
int start[MAXN];

int getSum(int a, int b) {
	return s[b] - s[a - 1];
}

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

	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		s[i] = s[i - 1] + a[i];
	}

	best[k] = s[k];
	start[k] = 1;
	int bestS = 1;
	int bestE = k;

	int gbest = -0x3f3f3f3f;

	for (int i = k + 1; i <= n; ++i) {

		int s1 = best[i - 1] + a[i];
		int s2 = a[i] + getSum(i - k, i - 1);

		if (s1 > s2) {
			best[i] = s1;
			start[i] = start[i - 1];
		}
		else {
			best[i] = s2;
			start[i] = i - k;
		}

		if (best[i] > gbest) {
			gbest = best[i];
			bestS = start[i];
			bestE = i;
		}
		
	}

	printf("%d %d %d", bestS, bestE, gbest);

	return 0;
}