Cod sursa(job #3355899)

Utilizator serbanbBrindescu Serban serbanb Data 27 mai 2026 15:08:05
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>

using namespace std;

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

int n,k;
int v[50005];
long long int ps[50005];
long long int dp[50005];
int l[50005];

void read()
{
    fin >> n >> k;
    for(int i = 1; i <= n; ++i){
        fin >> v[i];
        ps[i] = ps[i - 1] + v[i];
    }
}

void solve()
{
    dp[k] = ps[k];
    l[k] = 1;
    for(int i = k + 1; i <= n; ++i){
        if(dp[i - 1] + v[i] >= ps[i] - ps[i - k]){
            dp[i] = dp[i - 1] + v[i];
            l[i] = l[i - 1];
        }
        else{
            dp[i] = ps[i] - ps[i - k];
            l[i] = i - k + 1;
        }
    }
    long long int maxS = -2500000000;
    int st, dr;
    for(int i = k; i <= n; ++i){
        if(dp[i] > maxS){
            maxS = dp[i];
            st = l[i];
            dr = i;
        }
    }
    fout << st << ' ' << dr << ' ' << maxS;
}

int main()
{
    read();
    solve();
    return 0;
}