Pagini recente » Cod sursa (job #2619539) | Cod sursa (job #2305151) | Statistici Ana-Maria Simionescu (ana-maria.simi) | Cod sursa (job #1125509) | Cod sursa (job #2657662)
#include <fstream>
using namespace std;
int main(int argc, char *argv[]) {
ifstream in("secv2.in");
int n, k, a[50000];
in >> n >> k;
for (int i = 0; i < n; i++) in >> a[i];
in.close();
int dp[50000];
int seq[50000];
int start = 0;
for (int i = 0; i < k; i++) {
start += a[i];
seq[i] = 0;
}
dp[k - 1] = start;
seq[k - 1] = k - 1;
for (int i = k; i < n; i++) {
dp[i] = dp[i - 1] - a[i - k] + a[i];
seq[i] = k - 1;
}
for (int i = k; i < n; i++) {
if (dp[i - 1] > dp[i] || dp[i - 1] + a[i] > dp[i]) {
dp[i] = dp[i - 1] + a[i];
seq[i] = seq[i - 1] + 1;
}
}
int max = dp[k - 1];
int pos = k - 1;
for (int i = k; i < n; i++) {
if (max <= dp[i]) {
max = dp[i];
pos = i;
}
}
ofstream out("secv2.out");
out << pos + 1 - seq[pos] << " " << pos + 1 << " " << max;
out.close();
return 0;
}