Cod sursa(job #2922236)

Utilizator Teodor11Posea Teodor Teodor11 Data 6 septembrie 2022 20:00:34
Problema Secventa 2 Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.03 kb
#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;
}