Cod sursa(job #1005024)

Utilizator cont_de_testeCont Teste cont_de_teste Data 3 octombrie 2013 22:30:23
Problema Secventa 2 Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <iostream>
#include <fstream>
using namespace std;


const int MAX_SIZE = 50100;
const int oo = 2000000000;
int n, k;
int a[MAX_SIZE];
int mn[MAX_SIZE], ps[MAX_SIZE];

int sol = -oo, ls, rs;

void read() {
	ifstream fin("secv2.in");
	fin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		fin >> a[i];
		if (a[i] < 0) {
			mn[i] = a[i];
			ps[i] = i;
		}
		if (mn[i] > mn[i - 1]) {
			mn[i] = mn[i - 1];
			ps[i] = ps[i - 1];
		}
	}
}

void solve() {
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		int poz = max(0, i - k);
		sum += a[i];
		if (i >= k) {
			if (sol < sum - mn[poz]) {
				sol = sum - mn[poz];
				ls = ps[poz] + 1; rs = i;
			}
		}
	}
}

void write() {
	ofstream fout("secv2.out");
	fout << ls << ' ' << rs << ' ' << sol << '\n';
}


int main() {
	read(); solve(); write();	
}