Cod sursa(job #1882899)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 17 februarie 2017 16:23:24
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <cstdio>
using namespace std;

int pmin[50010], s[50010];

int main()
{
    FILE *in(fopen("secv2.in", "r")), *out(fopen("secv2.out", "w"));
    int n, k;

    fscanf(in, "%d%d", &n, &k);

    pmin[0] = 1;

    for (int i(1); i <= n; i++) {
        fscanf(in, "%d", &s[i]);
        s[i] += s[i - 1];
        if (s[i - 1] - s[pmin[i - 1] - 1] >= 0)
            pmin[i] = pmin[i - 1];
        else
            pmin[i] = i;
    }

    int sbest(-1000000000), st, dr;

    for (int i(k); i <= n; i++) {
        if (s[i] - s[pmin[i - k + 1] - 1] > sbest) {
            sbest = s[i] - s[pmin[i - k + 1] - 1];
            st = pmin[i - k + 1];
            dr = i;
        }
    }

    fprintf(out, "%d %d %d", st, dr, sbest);
    return 0;
}