Cod sursa(job #3143843)

Utilizator bent_larsenSturzu Antonio-Gabriel bent_larsen Data 2 august 2023 14:51:13
Problema Secventa 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>
using namespace std;

int main() {
	freopen("secv2.in", "r", stdin);
	freopen("secv2.out", "w", stdout);
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	
	for(int i = 0;i < n;++i)
		cin >> v[i];
	int dp[n], l[n];
	dp[0] = v[0];
	l[0] = 1;
	for(int i = 1;i < n;++i)
	{
		if(v[i] >= dp[i - 1] + v[i])
			dp[i] = v[i], l[i] = 1;
		else
			dp[i] = dp[i - 1] + v[i], l[i] = l[i - 1] + 1;
	}
	int sum = 0;
	for(int i = 0;i < k;++i)
		sum += v[i];
	int ans = sum;
	int end = k - 1, len = k;
	for(int i = k;i < n;++i)
	{
		sum += v[i] - v[i - k];
		if(sum > ans)
			ans = sum, end = i, len = k;
		if(sum + dp[i - k] > ans)
			ans = sum + dp[i - k], end = i, len = k + l[i - k];
	}
	cout << end - len + 2 << " " << end + 1 << " " << ans << "\n";
}