Cod sursa(job #944236)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 27 aprilie 2013 19:41:49
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>

using namespace std;

#define Nmax 50005
#define ll long long
#define inf ( 1 << 30 )

ll v[Nmax], sum[Nmax];

int N, K, inceput, sfarsit, SMAX = -inf;

void citire(){

    ifstream f("secv2.in");

    f >> N >> K;

    for ( int i = 1; i <= N; ++i )
        f >> v[i],
        sum[i] = sum[i - 1] + v[i];

    f.close();
}

void rezolva(){

    if ( N == K ){

        inceput = 1;
        sfarsit = N;
        SMAX = sum[N];

        return;
    }

    for ( int i = 1, S = 0; i <= N; ++i ){

        if ( sum[i] < S ){

            S = sum[i];
            inceput = i;
        }

        if ( sum[i] - S > SMAX && i - inceput > K )
            SMAX = sum[i] - S,
            sfarsit = i;

    }

    inceput++;
}

void afis(){

    ofstream g("secv2.out");

    g << inceput << " " << sfarsit << " " << SMAX;
}

int main(){

    citire();
    rezolva();
    afis();

    return 0;
}