Pagini recente » Cod sursa (job #2961081) | Cod sursa (job #796342) | Cod sursa (job #2027578) | Cod sursa (job #779081) | Cod sursa (job #1599325)
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int nmax = 50008;
int N,K,a[nmax],sum[nmax],best,p1,p2;
struct el{
int poz,x;
}st[nmax],dr[nmax];
inline void Precalc(){
int i,s = 0,j = 1;
for(i = 1; i <= N; ++i){
s+=a[i];
if(s < 0){
s = 0;
j = i+1;
st[i].poz = i;
st[i].x = a[i];
}
else{
st[i].x = s;
st[i].poz = j;
}
}
s = 0;
for(i = N; i; --i){
s+=a[i];
if(s < 0){
s = 0;
j = i-1;
dr[i].poz = i;
dr[i].x = a[i];
}
else{
dr[i].x = s;
dr[i].poz = j;
}
}
}
inline void Zoso(){
int i,sf,l,r;
best = -INF;
for(i = K; i <= N; ++i){
l = i-K+1; r = i;
sf = sum[i]-sum[i-K];
if(st[i-K].x>0)
sf+=st[i-K].x,l = st[i-K].poz;
if(dr[i+1].x>0)
sf+=dr[i+1].x,r = dr[i+1].poz;
if(sf > best){
best = sf;
p1 = l;
p2 = r;
}
}
}
int main(){
int i;
freopen ("secv2.in","r",stdin);
freopen ("secv2.out","w",stdout);
scanf("%d %d\n",&N,&K);
for(i = 1; i <= N; ++i){
scanf("%d ",&a[i]);
sum[i] = sum[i-1] + a[i];
}
Precalc();
Zoso();
if(!p1)++p1;
if(!p2)p2=N;
printf("%d %d %d\n",p1,p2,best);
return 0;
}