Cod sursa(job #2244165)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 22 septembrie 2018 12:44:37
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 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 = 6e6 + 6;

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 = k;
	
	l_curent = 1;
	
	for(int i = 1; i <= n; i++)
		cin >> v[i], v[i] += v[i - 1];
	
	for(int i = 1; i <= n; i++)
		best[i] = v[i] - v[max(i - k, 0)];
	
	ans = v[k];
	
	for(int i = k + 1; i <= n; i++)
	{
		if(v[i] - v[i - 1] + best[i - 1] < best[i])
			l_curent = i - k + 1;
		else
			best[i] = v[i] - v[i - 1] + best[i - 1];
		
		if(best[i] > ans)
				ans = best[i], l = l_curent, r = i;
	}
	
//	for(int i = 1; i <= n; i++)
//		cout << best[i] << ' ';
	
	cout << l << ' ' << r << ' ' << ans;
}

//Cazul 5 5 
//      -1 -1 -1 -1 -1