Pagini recente » Cod sursa (job #2519075) | Cod sursa (job #1832014) | Cod sursa (job #2698251) | Cod sursa (job #875599) | Cod sursa (job #209692)
Cod sursa(job #209692)
// http://infoarena.ro/problema/secv2
#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <deque>
using namespace std;
//deque<int> M;
const int NMAX = 50001;
int A[NMAX], M[NMAX], Used[NMAX];
long long S[NMAX], Ans[NMAX];
int main() {
freopen("secv2.in", "r", stdin);
freopen("secv2.out", "w", stdout);
int n, k;
scanf("%d %d", &n, &k);
int i;
for (i = 0; i < n; ++ i) {
scanf("%d", &A[i]);
if (i == 0) {
S[i] = A[i];
M[i] = 0;
} else {
S[i] = S[i - 1] + A[i];
if (S[M[i - 1]] < S[i])
M[i] = M[i - 1];
else
M[i] = i;
}
}
/*for (i = 0; i < n; ++ i)
printf("%d ", S[i]);
printf("\n");
for (i = 0; i < n; ++ i)
printf("%d\n", S[M[i]]);
printf("\n");*/
Ans[k - 1] = S[k - 1];
Used[k - 1] = 0;
for (i = k; i < n; ++ i) {
Ans[i] = S[i] - S[M[i - k]];
//printf("%lld %d\n", Ans[i], M[i - k]);
Used[i] = M[i - k] + 1;
}
int end = k, start = 1;
long long ans = - (1 << 63);
for (i = k - 1; i < n; ++ i) {
if (Ans[i] > ans) {
end = i + 1;
ans = Ans[i];
start = Used[i] + 1;
}
//printf("%d ", A[i]);
}
printf("%d %d %lld\n", start, end, ans);
/*for (i = 0; i < n; ++ i)
printf("%d ", S[i]);
printf("\n");*/
return 0;
}