Cod sursa(job #21456)

Utilizator amadaeusLucian Boca amadaeus Data 23 februarie 2007 17:10:01
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <vector>

using namespace std;

int main() {
	int N, K, p1, p2, a;
	long best, bi, si = 0;
	vector< long > vmin;
 	vector< int > pmin;
	
	ifstream f( "secv2.in" );
	ofstream g( "secv2.out" );

	f >> N >> K;
	vmin.resize( N - K + 1 );
	pmin.resize( N - K + 1 );

	vmin[ 0 ] = 0;
	pmin[ 0 ] = 0;
	
	for( int i=1; i<=N; i++ ) {
		f >> a;
		si += a;
		if( i <= N-K )
			if( vmin[ i-1 ] > si ) {
				vmin[i] = si;
				pmin[i] = i;
			}
			else {
				vmin[i] = vmin[i-1];
				pmin[i] = pmin[i-1];
			}
		if( i >= K ) {
			bi = si - vmin[ i-K ];
			if( i == K ) {
				best = bi;
				p1 = 1;
				p2 = K;
			}
			if( best < bi ) {
				best = bi;
				p1 = pmin[ i-K ] + 1;
				p2 = i;
			}
		}
	}
	g << p1 << " " << p2 << " " << best << endl;
	return 0;
}