Pagini recente » Cod sursa (job #63461) | Cod sursa (job #716878) | Cod sursa (job #3172301) | Cod sursa (job #2808000) | Cod sursa (job #2847230)
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int partial_sums[50001];
deque<int> partial_sums_indexes;
int main() {
int n, k, current_element;
fin >> n >> k;
for (int i = 1; i <= n; ++i) {
fin >> current_element;
partial_sums[i] = partial_sums[i - 1] + current_element;
}
int start_pos = 0, finish_pos = 0, max_sum = -1250000001;
partial_sums_indexes.push_back(0);
for (int i = 1; i <= n; ++i) {
if (partial_sums_indexes.size() && partial_sums[i] < partial_sums[partial_sums_indexes.back()]) {
partial_sums_indexes.push_back(i);
}
bool is_eliminated = false;
int last_eliminated_index;
while (partial_sums_indexes.size() && i - partial_sums_indexes.front() >= k) {
is_eliminated = true;
if (partial_sums[i] - partial_sums[partial_sums_indexes.front()] > max_sum) {
max_sum = partial_sums[i] - partial_sums[partial_sums_indexes.front()];
start_pos = partial_sums_indexes.front() + 1;
finish_pos = i;
}
last_eliminated_index = partial_sums_indexes.front();
partial_sums_indexes.pop_front();
}
if (is_eliminated) {
partial_sums_indexes.push_front(last_eliminated_index);
}
}
fout << start_pos << ' ' << finish_pos << ' ' << max_sum;
return 0;
}