Question

Am rezolvat problema pentru 70p pe pbinfo. La teste se presupune ca am depasit limita de timp (-30 punct).
Cod/ideas pentru 100p.

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

Answer 1

#include<cstdio>
#include<deque>
#define MAX_N 100000
using namespace std;

int v[MAX_N+1], n, k;
deque<int>deck;

int main()
{
    int i, smax, sum, Begin, End;
    FILE *fin, *fout;
    fin = fopen("secvk.in","r");
    fout = fopen("secvk.out","w");
    fscanf(fin,"%d%d",&n,&k);
    for(i=1; i<=n; i++)
        fscanf(fin,"%d",&v[i]);
    smax = -1;
    sum = 0;
    Begin = End = 0;
    for(i=1; i<=n; i++)
    {
        if(i <= k)
        {
            sum += v[i];
            deck.push_back(v[i]);
            if(i == k && sum > smax)
            {
                smax = sum;
                End = k;
                Begin = End - k + 1;
            }
        }
        else
        {
            sum -= deck.front();
            sum += v[i];
            deck.pop_front();
            deck.push_back(v[i]);
            if(sum > smax)
            {
                smax = sum;
                End = i;
                Begin = End - k + 1;
            }
        }
    }
    for(i=Begin; i<=End; i++)
        fprintf(fout,"%d ",v[i]);
    fprintf(fout,"\n");
    fclose(fout);
    fclose(fin);
    return 0;
}