Cod sursa(job #1248702)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 25 octombrie 2014 20:44:33
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <fstream>
#define DIM 100005
#define x first
#define y second
#define infile "secv2.in"
#define outfile "secv2.out"

using namespace std;

ifstream f(infile);
ofstream g(outfile);

int V[DIM], D[DIM], Partial_Sum_k[DIM];

int n, k;

pair<int, int> Pos[DIM];

int main() {
	f >> n >> k;
	for (int i = 1; i <= n; ++i)
		f >> V[i];
	for (int i = 1; i <= k; ++i)
		Partial_Sum_k[k] += V[i];
	for (int i = k + 1; i <= n; ++i)
		Partial_Sum_k[i] = Partial_Sum_k[i - 1] - V[i - k] + V[i];
	Pos[k].x = 1;
	Pos[k].y = k;
	D[k] = Partial_Sum_k[k];
	int SOL = D[k], sol_pos_start = 1, sol_pos_end = k;
	for (int i = k + 1; i <= n; ++i) {
		if (Partial_Sum_k[i] > D[i - 1] + V[i]) {
			D[i] = Partial_Sum_k[i];
			Pos[i].x = i - k + 1;
			Pos[i].y = i;
		}
		else {
			D[i] = D[i - 1] + V[i];
			Pos[i].x = Pos[i - 1].x;
			Pos[i].y = i;
		}
		if (SOL < D[i]) {
			SOL = D[i];
			sol_pos_start = Pos[i].x;
			sol_pos_end = Pos[i].y;
		}
	}
	g << sol_pos_start << " " << sol_pos_end << " " << SOL;
	return 0;
}

//Trust me, I'm the Doctor!