Cod sursa(job #274510)

Utilizator recviemAlexandru Pana recviem Data 9 martie 2009 20:11:51
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 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))

int interval(int a, int b){
	if ( a == 0)
		return sum[b];
	return (sum[b]-sum[a])+s[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-1;
	int m = 0;

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

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

	cout << a+1 << " " << b+1 << " " << interval(a,b);
	fout.close(), fin.close();
}

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