Cod sursa(job #3156981)

Utilizator cincadavidCinca David Andrei cincadavid Data 13 octombrie 2023 22:50:06
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <tuple>

using namespace std;

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

int main()
{
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
        if(i<k)
        {
            sum+=v[i];
        }
    }
    vector<pair<int,int> >maxsum(n,{0,0});
    maxsum[0].first=v[0];
    maxsum[0].second=0;
    int maxseq=v[0];
    int pos=0;
    for(int i=1;i<n;i++)
    {
        if(v[i]>maxseq+v[i])
        {
            maxseq=v[i];
            pos=i;
        }
        else
        {
            maxseq+=v[i];
        }
        maxsum[i]={maxseq,pos};
    }
    int res=sum;
    int st=0,en=k-1;
    for(int i=k;i<n;i++)
    {
        sum+=v[i]; sum-=v[i-k];
        //res=max(res,sum)
        //res=max(res,sum+maxsum[i-k]));
        if(res<sum)
        {
            res=sum;
            st=i-k+1;
            en=i;
        }
        if(res<sum+maxsum[i-k].first)
        {
            res=sum+maxsum[i-k].first;
            st=maxsum[i-k].second;
            en=i;
        }
    }
    cout<<st+1<<" "<<en+1<<" "<<res;

    return 0;
}