Pagini recente » Cod sursa (job #1248848) | Cod sursa (job #1501766) | Cod sursa (job #1658844) | Cod sursa (job #2228746) | Cod sursa (job #2922843)
#include <iostream>
#include <fstream>
using namespace std;
int n, k, sequence_sum, current_sum, start_point, end_point, v[50001], maxSum[50001], index[50001];
int main() {
ifstream fin("secv2.in");
ofstream fout("secv2.out");
fin >> n >> k;
for (int i = 1; i <= n; ++i) {
fin >> v[i];
if (maxSum[i - 1] + v[i] > v[i]) {
maxSum[i] = maxSum[i - 1] + v[i];
index[i] = index[i - 1];
} else {
maxSum[i] = v[i];
index[i] = i;
}
}
for (int i = 1; i <= k; ++i) {
current_sum += v[i];
}
sequence_sum = current_sum;
start_point = 1;
end_point = k;
for (int i = k + 1; i <= n; ++i) {
current_sum += v[i];
current_sum -= v[i - k];
//cout << "i = " << i << '\n';
//cout << "current_sum = " << current_sum << '\n';
//cout << "sequence_sum = " << sequence_sum << '\n';
//cout << "start_point = " << start_point << '\n';
//cout << "end_point = " << end_point << '\n';
if (sequence_sum < current_sum) {
sequence_sum = current_sum;
start_point = i - k + 1;
end_point = i;
//cout << "###Change 1###\n";
//cout << "sequence_sum = " << sequence_sum << '\n';
//cout << "start_point = " << start_point << '\n';
//cout << "end_point = " << end_point << '\n';
}
if (sequence_sum < current_sum + maxSum[i - k]) {
sequence_sum = current_sum + maxSum[i - k];
//cout << "###Change 2###\n";
start_point = index[i];
end_point = i;
//cout << "sequence_sum = " << sequence_sum << '\n';
//cout << "start_point = " << start_point << '\n';
//cout << "end_point = " << end_point << '\n';
}
//cout << '\n';
}
fout << start_point << ' ' << end_point << ' ' << sequence_sum;
return 0;
}