Cod sursa(job #697857)

Utilizator robertgbrrobertgbr robertgbr Data 29 februarie 2012 11:24:02
Problema Secventa 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<iostream>
#include<fstream>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
long int N,K,i,j[500001],bestSum,sum[50001],a[500001],best[50001],mini[50001],poz1,poz2;
void afis(){
	g<<poz1<<" ";
	g<<poz2<<" ";
	g<<bestSum<<'\n';
}
	
int main(){
	f>>N>>K;
	for(i=1;i<=N;i++){
		f>>a[i];
		sum[i]=a[i]+sum[i-1];}
	mini[0]=sum[0];
	bestSum=-2500001;
	for(i=1;i<=N;i++){
		best[i]=sum[i]-mini[i-K+1];
		if(mini[i-1]>sum[i]){
			mini[i]=sum[i];
		    j[i]=i+1;}
		else{
			mini[i]=mini[i-1];
			j[i]=j[i-1];
		}
		if(bestSum<best[i]){
			bestSum=best[i];
			poz1=j[i-K+1];
			poz2=i;
		}
	}
	afis();
	f.close();
	g.close();
	return 0;
}