Cod sursa(job #1809645)

Utilizator iulian_f2kGuraliuc Iulian iulian_f2k Data 19 noiembrie 2016 09:32:24
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
using namespace std;

vector<int> v, s, sMin, prec;
int N, k;

int main()
{
    freopen("secv2.in", "rt", stdin);
    freopen("secv2.out", "wt", stdout);
    scanf("%d%d", &N, &k);
    int ans = - INT_MAX, left, right;
    v.assign(N+2, 0);
    s.assign(N+2, 0);
    sMin.assign(N+2, 0);
    prec.assign(N+2, 0);
    for(int i = 1; i <= N; i++) {
        scanf("%d", &v[i]);
        s[i] = s[i - 1] + v[i];
        if(sMin[i - 1] < s[i])
            prec[i] = prec[i - 1];
        else
            prec[i] = i;
        sMin[i] = min(sMin[i - 1], s[i]);
    }
    for(int sf = k; sf <= N; sf++)
        if(s[sf] - sMin[sf - k] >= ans) {
            ans = s[sf] - sMin[sf - k];
            right = sf;
            left = prec[sf - k] + 1;
        }
    cout << left << ' ' << right << ' ' << ans << '\n';
    return 0;
}