Cod sursa(job #2430673)
Utilizator | Balanici 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;
}