Cod sursa(job #2631375)

Utilizator loraclorac lorac lorac Data 30 iunie 2020 11:08:50
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin("secv2.in");

ofstream fout("secv2.out");

int n, k, a, b;

long long v[50005], smax;

bool smax_empty = true;



int main() {

	fin >> n >> k;

	for (int i = 1; i <= n; ++i) {

		fin >> v[i];

		v[i] += v[i - 1];

	}

	for (int i = 1, min_j = 0; i <= n; ++i) {

		if ((i - min_j >= k && v[i] - v[min_j] > smax) || (smax_empty == true && i - min_j >= k)) {

			smax_empty = false;

			smax = v[i] - v[min_j];

			a = min_j + 1, b = i;

		}

		else if (i - min_j < k && i - k >= 0) {

			int min_j_aux = 0;

			for (int j = 1; j <= i - k; ++j)

				if (v[j] < v[min_j_aux])

					min_j_aux = j;

			if (v[i] - v[min_j_aux] > smax || smax_empty == true) {

				smax_empty = false;

				smax = v[i] - v[min_j_aux];

				a = min_j_aux + 1, b = i;

			}

		}

		if (v[i] < v[min_j])

			min_j = i;

	}

	fout << a << " " << b << " " << smax;

	return 0;

}