Cod sursa(job #2457248)

Utilizator Narcys01Ciovnicu Narcis Narcys01 Data 16 septembrie 2019 23:23:33
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <iostream>

using namespace std;

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

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

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

    fin >> n >> k;
    kadane[0] = -2000000000;
    for (i = 1; i <= n; i++)
    {
        fin >> v[i];
        kadane[i] = max(kadane[i-1] + v[i], v[i]);
    }
    s = 0;
    for (i = 1; i <= k; i++)
        s += v[i];

    smax = s;
    p1 = 1;
    p2 = k;
    for (i = k + 1; i <= n; i++)
    {
        s = s + v[i] - v[i-k];
        int c_smax = smax;
        smax = max(smax, max(s, s + kadane[i-k]));
        if (c_smax != smax)
            p2 = i;
    }
    int c_smax = smax;
    for(p1 = p2; c_smax != 0; p1--){
        c_smax -= v[p1];
    }
    p1++;

    fout << p1 << " " << p2 << " " << smax << "\n";
    return 0;
}