Cod sursa(job #2457218)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 16 septembrie 2019 22:03:08
Problema Secventa 2 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <fstream>
#include <iostream>

using namespace std;

int v[50004];
int t[50004];
int n, k;

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

    int i;
    int s, smax, p1, p2, poz;

    fin >> n >> k;
    for (i = 1; i <= n; i++)
    {
        fin >> v[i];
        t[i] = t[i-1] + v[i];
    }
    s = smax = t[k];
    p1 = 1;
    p2 = k;
    poz = 1;
    for (i = k+1; i <= n; i++)
    {
        t[i] = t[i-1] + v[i];
        if (s < 0) // exact k size
        {
            poz = i-k+1;
            s = t[i-1] - t[poz-1];
            //cout << s << " *\n";
        }
        else if (s >= 0) // exact k+1 size
        {
            if (v[poz] <= 0)
            {
                poz++;
                s = t[i-1] - t[poz-1];
            }
        }
        s += v[i];
        //cout << s << " +\n";
        if (s > smax)
        {
            smax = s;
            p1 = poz;
            p2 = i;
        }
    }
    /*while (v[p1] <= 0 && p1 <= p2-k)
    {
        p1++;
        smax = t[p2] - t[p1-1];
    }*/
    fout << p1 << " " << p2 << " " << smax << "\n";
    return 0;
}