Cod sursa(job #2094357)

Utilizator brczBereczki Norbert Cristian brcz Data 25 decembrie 2017 18:58:45
Problema Secventa 2 Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include<bits/stdc++.h>

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
#define bg begin
#define nd end
using namespace std;

#define maxn 100003

int a[maxn];
int dp[maxn];
int n,k;

int main() {

#ifndef ONLINE_JUDGE
	freopen("secv2.in", "r", stdin);
	freopen("secv2.out", "w", stdout);
#endif


	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int sumk = 0;
	for (int i = 0; i < n; ++i) {
		if (i == 0) dp[i] = a[i];
		else dp[i] = dp[i - 1] + a[i];
		if (i < k) sumk += a[i];
	}
	int mn = (1 << 30);
	int mx = sumk;
	int j = 0;
	int pozi = k-1, pozj = 0;
	for (int i = k; i < n; ++i) {
		if (dp[i - k] < mn) {
			j = i - k;
			mn = dp[i - k];
		}
		if ((dp[i] - mn) > mx) {
			mx = dp[i] - mn;
			pozj = j + 1;
			pozi = i;
		}
	}
	cout << pozj+1 << ' ' << pozi+1 << ' ' << mx << '\n';

	return 0;
}