Cod sursa(job #2446288)

Utilizator calinuxIorgulescu Calin calinux Data 7 august 2019 17:29:57
Problema Secventa 2 Scor 90
Compilator c-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>

#define MAXN	50000

void read(int *k, int *n, int v[MAXN+1]) {
	int i;
	freopen("secv2.in", "r", stdin);
	scanf("%d %d", n, k);
	for (i = 0 ; i < *n ; i++)
		scanf("%d", v + i);
}

void write(int st, int fn, int res) {
	freopen("secv2.out", "w", stdout);
	printf("%d %d %d\n", st, fn, res);
}

void solve(int k, int n, int v[MAXN+1]) {

	int S[MAXN+1], min[MAXN+1], minp[MAXN+1], res, res_st, res_fn;
	int i;

	min[0] = 0;
	minp[0] = -1;
	S[0] = v[0];

	for (i = 1 ; i < n ; i++) {
		S[i] = S[i-1] + v[i]; 
		min[i] = min[i-1];
		minp[i] = minp[i-1];
		if (S[i] < min[i]) {
			min[i] = S[i];
			minp[i] = i;
		}
	}

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

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

	for (i = 0 ; i < n ; i++)
		printf("%d ", minp[i]);
	printf("\n");
*/
	res = S[k - 1]; res_st = 0; res_fn = k - 1;
	for (i = k ; i < n ; i++) {
		if (S[i] - min[i - k] > res) {
			res = S[i] - min[i - k];
			res_st = minp[i - k] + 1;
			res_fn = i;
		}
	}

	write(res_st + 1, res_fn + 1, res);
}

int main(void) {

	int k, n, v[MAXN+1];
	read(&k, &n, v);
	solve(k, n, v);
	return 0;
}