Cod sursa(job #274294)

Utilizator recviemAlexandru Pana recviem Data 9 martie 2009 16:48:39
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.7 kb
#include <fstream>
#include <iostream>
using namespace std;

int n, k;
int s[60000],best[60000],sum[60000];

#define sFIN "secv2.in"
#define sFOUT "secv2.out"

#define FOR(i,b,c) for (int i = (b); i<(c); i++)
#define abs(a) ((a<0)?(-1*a):(a))

void mainLoop(){
	ifstream fin(sFIN);
	ofstream fout(sFOUT);

	fin >> n >> k;
	FOR(i,0,n){
		fin >> s[i];
		sum[i] = (i==0?s[i]:sum[i-1]+s[i]);
	}


	int a=0, b=k;

	FOR(i,1,n){
		if (s[i]<0 && sum[i] < sum[best[i-1]])
				best[i]=i;
		else
			best[i]=best[i-1];
	}

	FOR(i,k,n)
		if (sum[i] - sum[best[i-k]] > sum[b]-sum[a])
			a = best[i-k], b = i;

	fout << s[b] - s[a] << " " << a+1 << " " << b+1;
	fout.close(), fin.close();
}

int main() {
	mainLoop();
	return 0;
}