Cod sursa(job #3286461)

Utilizator blidar_lucian1Adrian Popescu blidar_lucian1 Data 14 martie 2025 11:17:16
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.11 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");

int n, k;
long long a[50001], sp[50001];

int main(){
    f >> n >> k;
    for (int i = 1; i <= n; i++){
        f >> a[i];
    }

    // Calculăm vectorul de sume parțiale: sp[0] = 0; sp[i] = a[1] + ... + a[i]
    sp[0] = 0;
    for (int i = 1; i <= n; i++){
        sp[i] = sp[i-1] + a[i];
    }

    // Inițial, pentru R = k, minimul este sp[0]
    long long bestSum = sp[k] - sp[0];
    int bestL = 1, bestR = k;

    long long minVal = sp[0];
    int minIndex = 0;

    // Parcurgem R de la k la n
    for (int R = k; R <= n; R++){
        // Actualizăm minimul prefixului pentru j în intervalul [0, R - k]
        if (R - k >= 0 && sp[R - k] < minVal) {
            minVal = sp[R - k];
            minIndex = R - k;
        }
        long long candidate = sp[R] - minVal;
        if (candidate > bestSum) {
            bestSum = candidate;
            bestL = minIndex + 1;
            bestR = R;
        }
    }

    g << bestL << " " << bestR << " " << bestSum;
    return 0;
}