Cod sursa(job #1732680)

Utilizator borcanirobertBorcani Robert borcanirobert Data 22 iulie 2016 11:47:25
Problema Secventa 2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <fstream>
using namespace std;

ifstream fin("secventa2.in");
ofstream fout("secventa2.out");

const int MAXN = 50005;
int a[MAXN];
int sum[MAXN];
int N, K;
int D[MAXN];
int t[MAXN];
int maxim, pi, pf;

void Read();
void Solve();

int main()
{
    Read();
    Solve();

    fin.close();
    fout.close();
    return 0;
}

void Read()
{
    int i, x;

    fin >> N >> K;
    for ( i = 1; i <= N; i++ )
    {
        fin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
}

void Solve()
{
    int i;

    D[K] = sum[K];
    t[K] = 1;

    for ( i = K + 1; i <= N; i++ )
        if ( D[i - 1] + a[i] >= sum[i] - sum[i - K] )
            D[i] = D[i - 1] + a[i], t[i] = t[i - 1];
        else
            D[i] = sum[i] - sum[i - K], t[i] = i - K + 1;

    for ( i = K; i <= N; i++ )
        if ( D[i] > maxim )
            maxim = D[i], pi = t[i], pf = i;

    fout << pi << ' ' << pf << ' ' << maxim << '\n';
}