Cod sursa(job #97561)

Utilizator tvladTataranu Vlad tvlad Data 7 noiembrie 2007 17:34:39
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>

const int N = 50000;

int n,k;
int a[N], b[N], c[N], s[N];

int main() {
	freopen("secv2.in","rt",stdin);
	freopen("secv2.out","wt",stdout);
	scanf("%d %d %d ",&n,&k,&a[0]);
	b[0] = a[0];
	c[0] = (a[0] > 0) ? a[0] : 0;
	s[0] = (a[0] > 0) ? 0 : -1;
	for (int i = 1; i<n; ++i) {
		scanf("%d",&a[i]);
		b[i] = b[i-1]+a[i];
		if (c[i-1] + a[i] >= 0) {
			c[i] = c[i-1]+a[i];
			s[i] = (s[i-1] == -1) ? i : s[i-1];
		} else {
			c[i] = 0;
			s[i] = -1;
		}
	}
	int sm = 0, fm = k-1, max = b[k-1];
	for (int i = k; i<n; ++i) {
		if (max < b[i]-b[i-k]+c[i-k]) {
			max = b[i]-b[i-k]+c[i-k];
			fm = i;
			sm = s[i-k];
			if (sm == -1) sm = i-k+1;
		}
	}
	printf("%d %d %d\n",sm+1,fm+1,max);
	return 0;
}