Cod sursa(job #3309390)

Utilizator Maria_MihailescuMihailescu Maria Maria_Mihailescu Data 4 septembrie 2025 10:41:59
Problema Secventa 2 Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 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 main(){
    int n, k;
    fin >> n >> k;
    for (int i = 1; i <= n; i++){
        fin >> v[i];
        sum[i] = sum[i - 1] + v[i];
    }
    int st = -1, dr = -1;
    long long rez = -1e15, s = 0;
    for (int i = k + 1; i <= n; i++){
        dp[i] = max(dp[i - 1] + v[i], sum[i] - sum[i - k]);
    }
    for (int i = k; i <= n; i++){
        if (dp[i] > rez){
            rez = dp[i];
            dr = i;
        }
    }
    for (int i = dr; i >= 1; i--){
        s = s + v[i];
        if (s == rez){
            st = i;
            break;
        }
    }
    fout << st << ' ' << dr << ' ' << rez;
    return 0;
}