Pagini recente » Istoria paginii runda/miercuri_ora_9.00/clasament | Cod sursa (job #1533126) | Istoria paginii runda/baaabaa/clasament | Cod sursa (job #1942401) | Cod sursa (job #2274027)
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
#define MAXN 50005
int n, k;
int a[MAXN];
int s[MAXN];
int best[MAXN];
int start[MAXN];
int getSum(int a, int b) {
return s[b] - s[a - 1];
}
int main() {
freopen("secv2.in", "r", stdin);
freopen("secv2.out", "w", stdout);
scanf("%d %d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
s[i] = s[i - 1] + a[i];
}
best[k] = s[k];
start[k] = 1;
int bestS = 1;
int bestE = k;
int gbest = s[k];
for (int i = k + 1; i <= n; ++i) {
int s1 = best[i - 1] + a[i];
int s2 = a[i] + getSum(i - k, i - 1);
if (s1 > s2) {
best[i] = s1;
start[i] = start[i - 1];
}
else {
best[i] = s2;
start[i] = i - k;
}
if (best[i] > gbest) {
gbest = best[i];
bestS = start[i];
bestE = i;
}
}
printf("%d %d %d", bestS, bestE, gbest);
return 0;
}