Cod sursa(job #2242040)

Utilizator alextodoranTodoran Alexandru Raul alextodoran Data 17 septembrie 2018 17:24:46
Problema Secventa 2 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

#define NM 50002

using namespace std;

int n, v[NM], sp[NM], k, mx, mxl, mxr;
int dp[NM], l[NM];

int main()
{
    ifstream fin ("secv2.in");
    ofstream fout ("secv2.out");
    fin >> n >> k;
    for(int i = 1; i <= n; i++)
    {
        fin >> v[i];
        sp[i] = sp[i - 1] + v[i];
    }
    for(int i = 1; i <= n - k + 1; i++)
    {
        if(dp[i - 1] > 0)
        {
            dp[i] = dp[i - 1] + v[i];
            l[i] = l[i - 1];
        }
        else
        {
            dp[i] = v[i];
            l[i] = i;
        }
    }
    for(int i = k; i <= n; i++)
        if(i == k || sp[i] - sp[i - k] + dp[i - k] > mx)
        {
            mx = sp[i] - sp[i - k] + dp[i - k];
            mxl = l[dp[i - k]];
            if(mxl == 0)
                mxl = 1;
            mxr = i;
        }
    fout << mxl << " " << mxr << " " << mx << "\n";
    return 0;
}