Cod sursa(job #2703747)

Utilizator Alex_tz307Lorintz Alexandru Alex_tz307 Data 9 februarie 2021 10:35:39
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

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

const int INF = 2e9;

int main() {
    int N, K;
    fin >> N >> K;
    vector<int> a(N + 1);
    vector<pair<int,int>> pref_min(N + 1);
    for(int i = 1; i <= N; ++i) {
        fin >> a[i];
        a[i] += a[i - 1];
        pref_min[i] = pref_min[i - 1];
        if(a[i] < pref_min[i].first)
            pref_min[i] = make_pair(a[i], i);
    }
    int ans = a[K], start = 1, End = K;
    for(int i = K + 1; i <= N; ++i) {
        int cand = a[i] - pref_min[i - K].first;
        if(cand > ans) {
            ans = cand;
            start = pref_min[i - K].second + 1;
            End = i;
        }
    }
    fout << start << ' ' << End << ' ' << ans << '\n';
}