Pagini recente » Cod sursa (job #2745632) | Cod sursa (job #3031274) | Cod sursa (job #382009) | Cod sursa (job #1112455) | Cod sursa (job #1096460)
/*
* File: secventa.cpp
* Author: Vlad
*
* Created on January 31, 2014, 2:05 AM
*/
#include <fstream>
using namespace std;
const int MAX_N = 50002;
int n, k;
long a[MAX_N], s[MAX_N], minS[MAX_N];
ifstream f("secv2.in");
ofstream g("secv2.out");
int main(int argc, char** argv) {
f >> n >> k;
for (int i = 1; i <= n; i++) {
f >> a[i];
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + a[i];
}
// Si - Min(Sj), j < i.
// compute min[i], minimum of sum ending in i
minS[1] = 1;
for (int i = 2; i <= n; i++) {
if (s[minS[i - 1]] > s[i]) {
minS[i] = i;
} else minS[i] = minS[i - 1];
}
int maxLeft = 1, maxRight = n, maxSum = s[n];
for (int i = k; i <= n; i++) {
if (s[i] - s[minS[i - k]] > maxSum) {
maxSum = s[i] - s[minS[i - k]];
maxLeft = minS[i - k] + 1;
maxRight = i;
}
}
g << maxLeft << ' ' << maxRight << ' ' << maxSum << '\n';
return 0;
}