Cod sursa(job #2891559)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 18 aprilie 2022 23:29:01
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <bits/stdc++.h>
#define NMAX 50005
#define MIN -25005

using namespace std;

int v[NMAX], sum[NMAX], minsum[NMAX];

int main()
{
	freopen("secv2.in", "r", stdin);
	freopen("secv2.out", "w", stdout);

	int n, k;
	int ans = MIN * NMAX, begin = 0, end = 0;
	cin >> n >> k;
	sum[0] = 0;
	minsum[0] = n + 1;
	sum[n + 1] = -MIN * NMAX;
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
		sum[i] = sum[i - 1] + v[i];
		if (sum[i] < sum[minsum[i - 1]])
			minsum[i] = i;
		else
			minsum[i] = minsum[i - 1];

		if (i >= k && ans < sum[i]) {
			ans = sum[i];
			begin = 1;
			end = i;
		}
	}

	for (int i = k + 1; i <= n; ++i) {
		if (ans < sum[i] - sum[minsum[i - k]]) {
			ans = sum[i] - sum[minsum[i - k]];
			begin = minsum[i - k] + 1;
			end = i;
		}
	}
	cout << begin << ' ' << end << ' ' << ans << '\n';
	return 0;
}