Pagini recente » Cod sursa (job #1696331) | Cod sursa (job #2021175) | Cod sursa (job #491176) | Cod sursa (job #2842856) | Cod sursa (job #205843)
Cod sursa(job #205843)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define nmax 50001
#define inf (1<<30)
int a[nmax],n,k;
int s[nmax],min[nmax],start,end,max,i,j;
int main(){
freopen("secv2.in","r",stdin);
freopen("secv2.out","w",stdout);
scanf("%d %d",&n,&k);
for(i=1;i<=n;++i)
scanf("%d", &a[i]),
s[i] = s[i-1] + a[i];
srand ( time(NULL) );
int randomshit = rand()%2;
if(n<3300&&randomshit)
{
max = -inf;
for(i=k;i<n;++i)
for(j=i;j<=n;++j)
if(s[j]-s[j-i] > max)
max = s[j]-s[j-i],start = j-i+1,end=j;
}
else
{
min[1] = 1;
for(i=2;i<=n;++i)
if(s[min[i-1]] > s[i])
min[i] = i;
else
min[i] = min[i-1];
max = s[k]; start = 1; end = k;
for(i=k+1; i<=n; ++i)
if(s[i] - s[min[i-k]] > max){
max = s[i] - s[min[i-k]];
start = min[i-k] + 1;
end = i;
}
if(start == 2 && a[1] > 0)
start = 1,max += a[1];
}
printf("%d %d %d",start,end,max);
return 0;
}