Cod sursa(job #2891556)

Utilizator VladNANegoita Vlad-Andrei VladNA Data 18 aprilie 2022 23:22:49
Problema Secventa 2 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>
#define NMAX 50005
#define MIN -25005
#define INF 1e9

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;
	cin >> n >> k;
	sum[0] = 0;
	minsum[0] = n + 1;
	sum[n + 1] = INF;
	for (int i = 1; i <= n; ++i) {
		cin >> v[i];
		sum[i] = sum[i - 1] + v[i];
		minsum[i] = min(minsum[i - 1], sum[i]);
		if (sum[i] < sum[minsum[i - 1]])
			minsum[i] = i;
		else
			minsum[i] = minsum[i - 1];
	}

	int ans = sum[k], begin = 1, end = k;
	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;
}