Cod sursa(job #1756598)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 13 septembrie 2016 07:44:54
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

const int NMAX = 50005;
const i64  INF = 1LL << 60;

int v[NMAX],
    l[NMAX];
i64 s[NMAX],
    d[NMAX];

int main(void) {
    freopen("secv2.in",  "r", stdin);
    freopen("secv2.out", "w", stdout);
    int n, k, a, b;
    i64 ant;

    ant = -INF;

    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; ++i) {
        scanf("%d", &v[i]);

        s[i] = s[i-1] + v[i];
        if(d[i-1] + v[i] < 0) {
            l[i] = i;
            d[i] = 0;
        }
        else {
            l[i] = l[i-1];
            d[i] = d[i-1] + v[i];
        }
    }

    for(int i=k; i<=n; ++i) {
        if(ant < s[i] - s[i-k] + d[i-k]) {
            ant = s[i] - s[i-k] + d[i-k];
            a   = l[i-k] + 1;
            b   = i;
        }
    }

    printf("%d %d %lld\n", a, b, ant);

    fclose(stdin);
    fclose(stdout);
    return 0;
}