Pagini recente » Cod sursa (job #2718396) | Cod sursa (job #1052143) | Cod sursa (job #630316) | Cod sursa (job #899667) | Cod sursa (job #2922236)
#include <iostream>
#include <fstream>
using namespace std;
int n, k, sequence_sum, current_sum, start_point, end_point, v[50001], maxSum[50001];
int main() {
ifstream fin("secv2.in");
ofstream fout("secv2.out");
fin >> n >> k;
for (int i = 1; i <= n; ++i) {
fin >> v[i];
maxSum[i] = max(maxSum[i - 1] + v[i], v[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";
for (int j = i - k; maxSum[j] >= 0 && j; --j) {
//cout << "j = " << j << '\n';
//cout << "maxSum[" << j - 1 << "] = " << maxSum[j - 1] << '\n';
start_point = j;
//cout << "start_point = " << start_point << "\n\n";
}
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;
}