Cod sursa(job #2765004)

Utilizator mousecanaalex mouse mousecana Data 24 iulie 2021 11:56:51
Problema Secventa 2 Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <climits>

using namespace std;
ifstream in("secv2.in");
ofstream out("secv2.out");

int v[50001];
struct structura {
	int val; // suma maxima a subsecv care se termina in i
	int lung_cur; // lungimea subsecv respective
};
structura v_final[50001];

void afisare(int n) {
	for (int i = 1; i <= n; i++)
		cout << v_final[i].val << " ";
	cout << endl;
}

int main() {
	int n, k, i;
	in >> n >> k;
	for (i = 1; i <= n; i++) {
		in >> v[i];
	}

	int s_max = INT_MIN, poz_max = 0;
	for (int i = 1; i <= k; i++) {
		v_final[k].val += v[i];
	}
	v_final[k].lung_cur = k;

	for (i = k + 1; i <= n; i++) {
		if (v_final[i - 1].val < 0 && v_final[i - 1].lung_cur == k) {
			v_final[i].val = v_final[i - 1].val + v[i] - v[i - k];
			v_final[i].lung_cur = k;
		}
		if (v_final[i - 1].val >= 0) {
			v_final[i].val = v_final[i - 1].val + v[i];
			v_final[i].lung_cur = v_final[i - 1].lung_cur + 1;
		}
		if (v_final[i].val > s_max) {
			s_max = v_final[i].val;
			poz_max = i;
		}
	}
	out << poz_max - v_final[poz_max].lung_cur + 1 << " " << poz_max << " " << s_max;
}