Pagini recente » Cod sursa (job #1998805) | Cod sursa (job #2029483) | Cod sursa (job #1406479) | Cod sursa (job #2221146) | Cod sursa (job #1640889)
#include <fstream>
#include <cstdio>
#define NMAX 50005
#define INF 5000005
using namespace std;
int n , k , sol , sum , ps[NMAX] , pf[NMAX] , s , f;
int a[NMAX] , ssm[NMAX] , sm[NMAX];
void read(int &x) {
int sign = 1;
char ch;
x = 0;
while(!isdigit(ch = getchar())) {
if(ch == '-') {
sign = -1;
}
else {
sign = 1;
}
}
do {
x = x * 10 + ch - '0';
}while(isdigit(ch = getchar()));
x *= sign;
}
int main() {
freopen("secv2.in" , "r" , stdin);
freopen("secv2.out" , "w" , stdout);
read(n) , read(k);
for(int i = 1 ; i <= n ; ++i) {
read(a[i]);
}
sum = -INF;
ps[0] = 1;
for(int i = 1 ; i <= n ; ++i) {
pf[i] = pf[i - 1];
ps[i] = ps[i - 1];
if(sum + a[i] >= a[i]) {
sum += a[i];
++pf[i];
}
else {
sum = a[i];
ps[i] = pf[i] = i;
}
ssm[i] = sum;
}
for(int i = 1 ; i <= n ; ++i) {
sm[i] = sm[i - 1] + a[i];
}
sol = sm[k];
s = 1;
f = k;
for(int i = k + 1 ; i <= n ; ++i) {
int qq = sm[i] - sm[i - k + 1] + ssm[i - k + 1];
if(qq > sol) {
sol = qq;
s = ps[i - k + 1];
f = i;
}
}
printf("%d %d %d" , s , f , sol);
return 0;
}