Cod sursa(job #3309393)

Utilizator Maria_MihailescuMihailescu Maria Maria_Mihailescu Data 4 septembrie 2025 10:57:04
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

 const int NMAX = 5e4;
int v[NMAX + 1];
int sum[NMAX + 1];
int dp[NMAX + 1];
int st2[NMAX + 1];

int main(){
    int n, k;
    fin >> n >> k;
    for (int i = 1; i <= n; i++){
        fin >> v[i];
        sum[i] = sum[i - 1] + v[i];
    }
    dp[k] = sum[k];
    st2[k] = 1;
    long long s = 0;
    for (int i = k + 1; i <= n; i++){
        dp[i] = max(dp[i - 1] + v[i], sum[i] - sum[i - k]);
        if (dp[i] == dp[i - 1] + v[i])
            st2[i] = st2[i - 1];
        else
            st2[i] = i - k + 1;
    }
    long long rez = dp[k];
    int dr = k, st = st2[k];
    for (int i = k; i <= n; i++){
        if (dp[i] > rez){
            rez = dp[i];
            dr = i;
            st = st2[i];
        }
    }
    fout << st << ' ' << dr << ' ' << rez;
    return 0;
}