Cod sursa(job #2922843)

Utilizator Teodor11Posea Teodor Teodor11 Data 10 septembrie 2022 12:37:38
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb
#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;
}