Cod sursa(job #1809679)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 19 noiembrie 2016 10:08:40
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>

using namespace std;

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

long long inc, sf, n, k, v[50010], smin[50010], smax = -10000000000, incmax, sfmax, pozmin[50010];

int main()
{
    int i, x;
    fin >> n >> k;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        v[i] = v[i - 1] + x;
        smin[i] = smin[i - 1];
        pozmin[i] = pozmin[i - 1];
        if (smin[i] > v[i])
        {
            smin[i] = v[i];
            pozmin[i] = i;
        }
    }
    smin[0] = 0;
    for (i = k; i <= n; i++)
    {
        if (v[i] - smin[i - k] > smax)
        {
            smax = v[i] - smin[i - k];
            incmax = pozmin[i - k] + 1;
            sfmax = i;
        }
    }
    fout << incmax << ' ' << sfmax << ' ' << smax << '\n';
    fout.close();
    return 0;
}