Cod sursa(job #2244152)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 22 septembrie 2018 12:23:25
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
//#include <bits/stdc++.h>
#include <fstream>
#include <vector>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iomanip>
 
using namespace std;

const int INF = 0x3f3f3f3f;

ifstream cin("secv2.in");
ofstream cout("secv2.out");

const int N = 5e4 + 7;

int ans;
int v[N];
int best[N];


main()
{
	int n, k;
	cin >> n >> k;
	
	int l_curent = 0;
	
	int l, r;
	
	l = 1;
	r = 1;
	
	l_curent = 1;
	
	for(int i = 1; i <= n; i++)
		cin >> v[i], v[i] += v[i - 1];
	
	for(int i = 1; i <= k; i++)
		best[i] = v[i];
	
	ans = v[k];
	
	for(int i = k + 1; i <= n; i++)
	{
		if(v[i] - v[i - 1] + best[i - 1] < v[i] - v[i - k])
			l_curent = i - k + 1, best[i] = v[i] - v[i - k];
		else
			best[i] = best[i - 1] + v[i] - v[i - 1];
		
		if(best[i] > ans)
				ans = best[i], l = l_curent, r = i;

	}
	
//	for(int i = 1; i <= n; i++)
//		cout << DP[i] << ' ';
	
	cout << l << ' ' << r << ' ' << ans;
}