Cod sursa(job #2430673)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 15 iunie 2019 20:37:26
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
#define Dim 50009
using namespace std;
ifstream f("secv2.in");
ofstream g("secv2.out");
int N,K,V[Dim],dp[Dim],nr[Dim],S[Dim];
int start,stop,ans;

int main()
{
    f>>N>>K;
    for(int i=1;i<=N;i++)
    {
        f>>V[i];
        S[i]=S[i-1]+V[i];
        if(dp[i-1]>0)
        {
            dp[i]=dp[i-1]+V[i];
            nr[i]=nr[i-1]+1;
        }
        else
        {
            dp[i]=V[i];
            nr[i]=1;
        }
    }
    ans=INT_MIN;
    for(int i=K;i<=N;i++)
    {
        if(nr[i]>=K)
        {
            if(dp[i]>ans)
            {
                ans=dp[i];
                stop=i;
                start=i-nr[i]+1;
            }
        }
        else
        {
            int ret=dp[i]+S[i-nr[i]]-S[i-K];
            if(ret>ans)
            {
               ans=ret;
               stop=i;
               start=i-K+1;
            }
        }
    }
    g<<start<<" "<<stop<<" "<<ans<<'\n';

    return 0;
}