Cod sursa(job #2891553)

Utilizator matthriscuMatt . matthriscu Data 18 aprilie 2022 23:00:05
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <bits/stdc++.h>
using namespace std;

#define problem "secv2"
#define NMAX 50005

int v[NMAX], sum_part[NMAX];

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

	int n, k;
	scanf("%d%d", &n, &k);

	int ans = INT_MIN, start = 1, end = k;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &v[i]);
		sum_part[i] = sum_part[i - 1] + v[i];
		if (i >= k && sum_part[i] > ans) {
			ans = sum_part[i];
			end = i;
		}
	}

	deque<int> dq;

	for (int i = 1; i <= n; ++i) {
		if (dq.front() <= i - k && sum_part[i] - sum_part[dq.front()] > ans) {
			ans = sum_part[i] - sum_part[dq.front()];
			start = dq.front() + 1;
			end = i;
		}
		while (!dq.empty() && sum_part[dq.back()] >= sum_part[i])
			dq.pop_back();
		dq.push_back(i);
	}

	printf("%d %d %d\n", start, end, ans);
}