Cod sursa(job #2714884)

Utilizator andreiiorgulescuandrei iorgulescu andreiiorgulescu Data 2 martie 2021 17:27:07
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

int sumpart[50005],a[50005],smax,s,i,slast,stot,n,k,xc = 1,x = 1,y;

int main()
{
    in >> n >> k;
    y = k;
    for (i = 1; i <= n; i++)
    {
        in >> a[i];
        s += a[i];
        sumpart[i] = s;
    }
    smax = s = sumpart[k];
    for (i = k + 1; i <= n; i++)
    {
        stot = s + a[i];
        slast = sumpart[i] - sumpart[i - k];
        s = max(stot,slast);
        if (s == slast)
            xc = i - k + 1;
        if (s > smax)
        {
            smax = s;
            x = xc;
            y = i;
        }
    }
    out << x << " " << y << " " << smax;
    return 0;
}
/*
la pasul i>k:
la inceput sc este cea mai mare suma care se poate forma cu cel putin k termeni si se termina pe pozitia i-1
vrei sa obtii cea mai mare suma care se poate forma cu cel putin k termeni si se termina pe pozitia i
adunand v[i] la sc obtii cea mai mare suma care se poate forma cu cel puin k+1 termeni si se termina pe pozitia i
pemtru a trece de la "cel putin k+1" la "cel putin k" trebuie luat in considerare "exact k"
{1}
adica sc devine max(sc+v[i], suma ultimilor exact k)
suma ultimilor exact k este sum[i] - sum[i-k]
unde sum[i] = v[1] + v[2] + ... + v[i]
*/