Cod sursa(job #722475)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 24 martie 2012 17:07:28
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<fstream>
using namespace std;
int v[50001],sum[50001];
int main(){
	int smax=-1000000000,sc,i,k,stmax,drmax,stc,n;
	ifstream in("secv2.in");
	ofstream out("secv2.out");
	in>>n>>k;
	for(i=1;i<=n;i++)
		sum[i]=0;
	for(i=1;i<=n;i++){
		in>>v[i];
		sum[i]=sum[i-1]+v[i];
	}
	smax=sc=sum[k];
	stc=stmax=1;
	drmax=k;
	for(i=k+1;i<=n;i++){
		if(sum[i]-sum[i-k]>sc+v[i]){
			sc=sum[i]-sum[i-k];
			stc=i-k+1;
		}else sc=sc+v[i];
		if(sc>smax){
			stmax=stc;
			drmax=i;
			smax=sc;
		}
	}
	out<<stmax<<' '<<drmax<<' '<<smax<<'\n';
	in.close();
	out.close();
	return 0;
}