Cod sursa(job #195923)

Utilizator webspiderDumitru Bogdan webspider Data 23 iunie 2008 12:24:40
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

#define pb push_back
#define sz size()
#define ff first
#define ss second

const int maxN = 50001;
const int INF = ( 1<<31 );

int N,K;
int sumP[ maxN ];
int subS[ maxN ];
int ST, END, mSUM;
int sM = 0;
int fST;

int main()
{
    int el;
#ifdef PC_COMPILE
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
#else
	freopen("secv2.in","r",stdin);
	freopen("secv2.out","w",stdout);
#endif
    mSUM = 0;
    fST = 0;

    scanf("%d %d\n", &N, &K );
    for ( int i = 0; i < N; i++ ) {
        scanf("%d\n", &el );
        if ( i == 0 ) sumP[i] = el;
        else sumP[ i ] = sumP[i-1] + el;
        if ( i == K-1 ) {
            sM = sumP[ i ];
            END = i;
        }
        if ( i >= K ) {
            if ( sumP[ i-K ] < mSUM ) {
                mSUM = sumP[ i-K ];
                ST = i-K+1;
            }
            if ( sumP[i] - mSUM > sM ) {
                sM = sumP[i] - mSUM;
                fST = ST;
                END = i;
            }
        }
        //printf("[%d] %d %d %d %d (%d)\n", i, ST, END, sM, mSUM, sumP[i] );
    }

    printf("%d %d %d\n", fST+1, END+1, sM);

	return 0;
}