Cod sursa(job #2628312)

Utilizator CosminMorarMorar Cosmin Andrei CosminMorar Data 15 iunie 2020 15:04:01
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("secv2.in");
ofstream fout("secv2.out");
int n, k, nr, v[50100], sp[50100], end_point[50100];

int main() {
	fin >> n >> k;
	for (int i = 1; i <= n; i++) {
		fin >> v[i];
		sp[i] = sp[i - 1] + v[i];
	}

	int suma = -1;
	for (int i = n; i >= 1; i--) {
		if (suma < 0)
			end_point[i] = i;
		else
			end_point[i] = end_point[i + 1];
		suma = max(v[i], suma + v[i]);
	}

	int suma_max = INT_MIN, in_max, sf_max;
	for (int i = 1; i <= n - k + 1; i++) {
		int suma = sp[end_point[i + k - 1]] - sp[i - 1];
		int sf = end_point[i + k - 1];
		while (sf - i + 1 < k) {
			sf++;
			suma += sp[end_point[sf]];
		}

		if (suma > suma_max) {
			suma_max = suma;
			in_max = i;
			sf_max = sf;
		}
	}

	fout << in_max << ' ' << sf_max << ' ' << suma_max;
    return 0;
}