Cod sursa(job #1833998)

Utilizator Coroian_DavidCoroian David Coroian_David Data 23 decembrie 2016 17:24:18
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

#include <climits>

using namespace std;

FILE *f, *g;

struct minim
{
    int poz, nr;
};

minim mn[50001];

int s[50001];

int n, k;

void readFile()
{
    f = fopen("secv2.in", "r");

    fscanf(f, "%d%d", &n, &k);

    int i, nr;

    mn[0].nr = INT_MAX;

    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d", &nr);

        s[i] = s[i - 1] + nr;

        if(s[i] < mn[i - 1].nr)
        {
            mn[i].nr = s[i];

            mn[i].poz = i;
        }

        else
            mn[i] = mn[i - 1];

        //printf("%d %d\n", s[i], mn[i].nr);
    }

    fclose(f);
}

int mx, dr, st;

void solve()
{
    int i;

    mx = s[k];

    st = 1;

    dr = k;

    for(i = k + 1; i <= n; i ++)
    {
        if(s[i] - mn[i - k].nr > mx)
        {
            mx = s[i] - mn[i - k].nr;

            dr = i;

            st = mn[i - k].poz + 1;
        }
    }
}

void printFile()
{
    g = fopen("secv2.out", "w");

    fprintf(g, "%d %d %d\n", st, dr, mx);

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}