Cod sursa(job #2891014)

Utilizator mirunavramMiruna Avram mirunavram Data 17 aprilie 2022 12:49:04
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.4 kb
#include<bits/stdc++.h>



using namespace std;



int n,sol = INT_MIN,k,indexDreapta,indexStanga,indexFinalStanga;
int sp[6000005],mp[6000005],pos[50005];



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



    fin>>n>>k;



    sp[0]=0;
    mp[0] = 0;
/////pos[i] = pozitia la care se afla mp[i] (indicele sumei partiale minime dintre s[0] si s[i])
    pos[0] = 0;
    for(int i=1;i<=n;i++)





    {
        int x;
        fin>>x;
        sp[i] = sp[i-1] + x;





        if(i >= k){



            int val = sp[i] - mp[i-k];





            if(val > sol){





                sol = val;
                indexDreapta = i;
                indexFinalStanga = pos[i-k] + 1;
            }
        }





/**
Ce se schimba de la i la i+1
{1}
{1}
{1}
Pentru i, ne intereseaza ca lungimea sa fie >=k, deci ne intereseaza sumele partiale de la sp[0] pana la sp[i-k]
Pentru i+1, ne intereseaza ca lungimea sa fie >=k, deci ne intereseaza sumele partiale de la sp[0] pana la sp[i-k+1]
{1}
{1}
{1}
Va trebui sa adaugama sp[i-k+1]
**/
//if(i>=k && sp[i-k+1] < mp[i-k] ){
// indexStanga = i-k+2;
//}
//mp[i] = min(mp[i-1],sp[i]);
        if(sp[i]<mp[i-1])
        {
            mp[i] = sp[i];
            pos[i] = i;
        }
        else
        {
            mp[i] = mp[i-1];
            pos[i] = pos[i-1];
        }
    }



    fout<<indexFinalStanga<<" "<<indexDreapta<<" "<<sol<<'\n';



    return 0;
}