Cod sursa(job #2714858)

Utilizator DragosC1Dragos DragosC1 Data 2 martie 2021 16:46:04
Problema Secventa 2 Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <deque>
using namespace std;

int n, k, st, dr;
int a[50001];
const int Inf = 1e9;
int smax = -Inf;

void read() {
	int i;
	ifstream f("secv2.in");
	f >> n >> k;
	for (i = 1; i <= n; i++)
		f >> a[i];
	f.close();
}

void solve() {
	int i;
	for (i = 1; i <= n; i++)
		a[i] += a[i - 1];
	deque<int> dq;
	i = 1;
	while (i < k) {
		dq.emplace_back(i);
		i++;
	}
	for (; i <= n; i++) {
		dq.push_back(i);
		if (dq.size() >= k && a[dq.back()] - a[dq.front() - 1] > smax) {
			smax = a[dq.back()] - a[dq.front() - 1];
			st = dq.front();
			dr = dq.back();
		}
		while (dq.size() > k && a[dq.back()] - a[dq.front()] >= a[dq.back()] - a[dq.front() - 1])
			dq.pop_front();
	}
}

void output() {
	ofstream g("secv2.out");
	g << st << ' ' << dr << ' ' << smax;
	g.close();
}

int main() {
	read();
	solve();
	output();
	return 0;
}