Cod sursa(job #2175276)

Utilizator alexge50alexX AleX alexge50 Data 16 martie 2018 16:23:58
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#include <queue>

struct cell
{
    int pos, value;
};

int main()
{
    FILE *fin = fopen("secv2.in", "r"),
         *fout = fopen("secv2.out", "w");
    int n, k;
    int sum;
    int max;
    std::queue<cell> Q;
    int begin, end;

    fscanf(fin, "%d %d ", &n, &k);
    sum = 0;
    max = 0;
    for(int i = 1; i <= n; i++)
    {
        int x;

        fscanf(fin, "%d", &x);

        if(i < k)
            Q.push({i, x}), sum += x;
        else
        {
            while(!Q.empty() && i - Q.front().pos >= k && sum - Q.front().value < x)
            {
                sum -= Q.front().value;
                Q.pop();
            }

            Q.push({i, x});
            sum += x;
        }

        if(max < sum)
        {
            max = sum;
            begin = Q.front().pos;
            end = i;
        }
    }

    fprintf(fout, "%d %d %d\n", begin, end, max);

    fclose(fin);
    fclose(fout);
    return 0;
}