Cod sursa(job #1219469)

Utilizator andreas.chelsauAndreas Chelsau andreas.chelsau Data 14 august 2014 12:09:26
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;

int n,k,a[50005],s[50005];

int main(){
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i = 0; i < n; i++){
		scanf("%d",&a[i]);
		s[i + 1] = s[i] + a[i];
	}
	ll max = (ll)s[k],bestSum = (ll)s[k];
	int startPoz = 0,endPoz = k - 1,finStartPoz = 0;
	for(int i = k + 1; i < n; i++){
		max += (ll)a[i];
		if(max <= (ll)(s[i + 1] - s[i - k + 1])){
			max = (ll)(s[i + 1] - s[i - k + 1]);
			startPoz = i - k + 1;
		}
		
		if(bestSum < max){
			bestSum = max;
			endPoz = i,
			finStartPoz = startPoz;
		}
	}
	printf("%d %d %lld\n",finStartPoz + 1,endPoz + 1,bestSum);
	return 0;
}