Se dă un șir cu n numere naturale și un număr k.

Cerinţa

Să se determine o secvență de elemente de lungime k cu suma elementelor maximă.

Date de intrare

Fişierul de intrare secvk.in conţine pe prima linie numerele n și k, iar pe a doua linie n numere naturale separate prin spaţii.

Date de ieşire

Fişierul de ieşire secvk.out va conţine pe prima linie k numere, reprezentând elementele secvenței cerute.

Restricţii şi precizări

• 1 ≤ k ≤ n ≤ 100000
• numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1000
• dacă există mai multe secvențe de lungime k cu suma maximă se va afișa prima

Exemplu

secvk.in

8 3
5 6 1 2 6 6 4  3

secvk.out

6 6 4

Explicație

Sumele care se pot obține sunt: 12 9 9 14 16 13. Suma maximă este 16 și se obține pentru secvența 6 6 4

#include <bits/stdc++.h>


using namespace std;

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

int n , a[100001] , k;
int main()
{
    fin >> n >> k;
    for(int i = 1 ; i <= n ; ++i)
        fin >> a[i];
    int smax=0, dr = 0 , s=0;
    for(int i = 1 ; i < k ; ++i)
        s+=a[i];
    for(int i = k ; i <= n ; ++i)
    {
        s+=a[i];
        s-=a[i-k];
        if(s>smax)
        {
            smax=s;
            dr=i;
        }
    }
    for(int i = dr - k + 1 ; i <= dr ; ++i)
        fout << a[i] << ' ';
    
    fin.close();
    fout.close();
    
    return 0;
}