Cod sursa(job #3322391)

Utilizator FistfullOfDollar059Andrei Marin Popa FistfullOfDollar059 Data 13 noiembrie 2025 19:14:52
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int n, k;
    fin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) fin >> a[i];

    // prefix sums of size n+1
    // pref[i] = sum of a[0..i-1]
    vector<int> pref(n + 1, 0);
    for (int i = 1; i <= n; i++)
        pref[i] = pref[i - 1] + a[i - 1];

    // we want: max(pref[dr] - pref[st]) with dr - st >= k
    int bestSum = -1e9, bestL = 1, bestR = k;

    // keep track of the minimum prefix sum available for the st candidate
    int minPref = 0;          // pref[0]
    int minPrefPos = 0;

    for (int dr = k; dr <= n; dr++) {
        // the candidate st can go from 0..dr-k
        int stLimit = dr - k;

        // update minimum prefix sum up to stLimit
        if (pref[stLimit] < minPref) {
            minPref = pref[stLimit];
            minPrefPos = stLimit;
        }

        int sum = pref[dr] - minPref;
        if (sum > bestSum) {
            bestSum = sum;
            bestL = minPrefPos + 1;
            bestR = dr;
        }
    }

    fout << bestL << " " << bestR << " " << bestSum;
}