Cod sursa(job #1714074)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 7 iunie 2016 12:57:59
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <iostream>
#include <cstdio>
#define MAXN 50050

using namespace std;

int n, k, a[MAXN];
int sum[MAXN], minsum[MAXN], dsum[MAXN], dmsum[MAXN];

void citire()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", a+i);
}

void pre()
{
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i-1] + a[i];
    minsum[1] = 1;
    for (int i = 2; i <= n; i++)
        if (sum[i] < sum[minsum[i-1]])
            minsum[i] = i;
        else
            minsum[i] = minsum[i-1];
    for (int i = n; i; --i)
        dsum[i] = dsum[i+1] + a[i];
    dmsum[n] = n;
    dmsum[n+1] = n+1;
    for (int i = n-1; i; --i)
        if (dsum[i] < dsum[dmsum[i+1]])
            dmsum[i] = i;
        else
            dmsum[i] = dmsum[i+1];
    for (int i = 1; i <= n; i++)
    {
        if (sum[i] > 0) sum[i] = 0;
        if (dsum[i] > 0) dsum[i] = 0;
    }
}

void solve()
{
    int best = 1000, pos;
    for (int i = 0; i <= n-k; i++)
    {
        int sterg = sum[minsum[i]] + dsum[dmsum[i+k+1]];
        if (sterg < best)
        {
            best = sterg;
            pos = i;
        }
    }
    int s = 0;
    for (int i = 1; i <= n; i++) s += a[i];
    printf("%d %d %d\n", minsum[pos]+1, dmsum[pos+k+1]-1, s - sum[minsum[pos]] - dsum[dmsum[pos+k+1]]);

}

int main()
{
    freopen("secv2.in", "r", stdin);
    freopen("secv2.out", "w", stdout);

    citire();
    pre();
    solve();

    return 0;
}