Cod sursa(job #94309)

Utilizator tvladTataranu Vlad tvlad Data 22 octombrie 2007 17:05:39
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 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) ? a[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];
		} else {
			c[i] = 0;
			s[i] = 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;
			int ss = s[i-k];
			while (c[ss] == 0 && ss <= i-k) ++ss;
			sm = ss;
		}
	}
	printf("%d %d %d\n",sm+1,fm+1,max);
	return 0;
}