Cod sursa(job #2726530)

Utilizator AlexZeuVasile Alexandru AlexZeu Data 21 martie 2021 09:43:53
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
 
ifstream fin("secv2.in");
ofstream fout("secv2.out");
 
int n, k, x, dp[50100], best_sum = INT_MIN, Beg, End;

int main(){
    fin.tie(0);
    ios::sync_with_stdio(0);
    fin >> n >> k;
    // dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        fin >> x;
        dp[i] = dp[i - 1] + x;
    }
    int minim = dp[0];
    int pozitie_minim = 1;
    // S[A..B] = S[A] - S[B - 1];
    for (int i = k; i <= n; ++i) {
        int sum = dp[i] - dp[pozitie_minim - 1];
        if (sum > best_sum) {
            best_sum = sum;
            Beg = pozitie_minim;
            End = i;
        }
        if (minim > dp[i - k]) {
            minim = dp[i - k];
            pozitie_minim = i - k + 1;
        }
    }
    fout << Beg << " " << End << " " << best_sum;
    return 0;
}