Cod sursa(job #2714854)

Utilizator vladboss2323Ciorica Vlad vladboss2323 Data 2 martie 2021 16:41:57
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <iostream>
#include <fstream>
using namespace std;

int sum[50001];
int main()
{
    ifstream in("secv2.in");
    ofstream out("secv2.out");
    int n,k,smax,sc,pc,umax,pmax,i,a[50001];
    in>>n>>k;
    for(i = 1; i <= k; i++)
    {
        in>>a[i];
        sum[i] = sum[i-1] + a[i];
    }
    sc = smax = sum[k];
    pc = pmax = 1;
    umax = k;
    for(i = 1+k; i <= n; i++)
    {
        in>>a[i];
        sum[i] = sum[i-1] + a[i];
        if (sum[i] - sum[i-k] > sc + a[i])
        {
            sc = sum[i] - sum[i-k];
            pc = i - k + 1;
        }
        else
            sc += a[i];

        if (sc > smax)
        {
            smax = sc;
            pmax = pc;
            umax = i;
        }
    }
    out<<pmax<<" "<<umax<< " "<<smax;
}
/*
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"

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]
*/