Cod sursa(job #430896)

Utilizator eukristianCristian L. eukristian Data 31 martie 2010 14:07:33
Problema Secventa 2 Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <climits>
using namespace std;

int N,K,v[50000];

void read_data();
void solve();
int main()
{
	read_data();
	solve();
	return 0;
}

void read_data()
{
	ifstream f("secv2.in");
	f >> N >> K;
	for (int i = 1 ; i <= N ; ++i)
		f >> v[i];
	f.close();
}

void solve()
{
	int structura[50000],structura2[50000],sume[50000],prev[50000];
	for (int i = 0 ; i < N ; ++i)
	{
		structura[i] = structura2[i] = sume[i] = prev[i] = 0;
	}
	ofstream g("secv2.out");
	structura2[1] = v[1];
	for (int k = 2; k <= N ; ++k)
	{
		if (structura2[k - 1] > 0)
		{
			structura2[k] = structura2[k - 1] + v[k];
			prev[k] = prev[k - 1];
		}
		else
		{
			structura2[k] = v[k];
			prev[k] = k;
		}
	}
	for (int i = 1 ; i <= N - K + 1; ++i)
	{
		int sum = 0, j;
		for (j = i ; j <= i + K - 1 ; ++j)
		{
			sum = sum + v[j];
		}
		j--;
		sume[j] = sum;
	}
	int start = 0,max = INT_MIN,last = 0;
	for (int i = K ; i <= N ;++i)
	{
		structura[i] = sume[i];
		if (structura2[i - K] > 0)
			structura[i] += structura2[i - K];
		if (structura[i] > max)
		{
			max = structura[i];
			start = prev[structura2[i - K]];
			last = i;
		}
	}
	for (int i = K ; i <= N ; ++i)
		if (structura[i] > max)
			max = structura[i];
	if (!start)
		start++;
	g << start << " " << last << " " << max << endl;
}