Cod sursa(job #2457234)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 16 septembrie 2019 22:47:21
Problema Secventa 2 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 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)
        {
            poz = i-k+1;
            s = t[i-1] - t[poz-1];
        }
        else if (s >= 0 && v[poz] < 0)
        {
            poz++;
            s = t[i-1] - t[poz-1];
        }
        //else
            s += v[i];
        if (s > smax)
        {
            smax = s;
            p1 = poz;
            p2 = i;
        }
    }
    for (i = p1; i >= 0; --i)
    {
        s = t[p2] - t[i-1];
        if (s > smax)
        {
            p1 = i;
            smax = s;
        }
    }
    fout << p1 << " " << p2 << " " << smax << "\n";
    return 0;
}