Cod sursa(job #2631333)

Utilizator loraclorac lorac lorac Data 29 iunie 2020 22:05:06
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
using namespace std;
ifstream cin("secv2.in");
ofstream cout("secv2.out");
const int lim=50005;
int v[lim],p[lim];
pair<int,int> st[lim],dr[lim];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
        p[i]=p[i-1]+v[i];
    }
    for(int i=1;i<=n;++i)
    {
        if(st[i-1].first<0) st[i]={v[i],i};
        else st[i]={st[i-1].first+v[i],st[i-1].second};
    }
    for(int i=n;i>=1;--i)
    {
        if(dr[i+1].first<0) dr[i]={v[i],i};
        else dr[i]={dr[i+1].first+v[i],dr[i+1].second};
    }
    int ans=p[k],l=1,r=k;
    for(int i=1;i+k<=n+1;++i)
    {
        int base=p[i+k-1]-p[i-1]+max(0,st[i-1].first)+max(0,dr[i+k].first);
        if(base>ans)
        {
            ans=base;
            if(st[i-1].first<=0) l=i;
            else l=st[i-1].second;
            if(dr[i+k].first<=0) r=i+k-1;
            else r=dr[i+k].second;
        }
    }
    cout<<l<<' '<<r<<' '<<ans<<'\n';
    return 0;
}