Cod sursa(job #1610848)

Utilizator Firealex2Rotileanu Alexandru Firealex2 Data 23 februarie 2016 19:30:40
Problema Secventa 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>

using namespace std;

ifstream fi("secv2.in");
ofstream fo("secv2.out");

int v[50001];

int main()
{
	int sc, pc, uc, smax, start=0, ultim=0, n, k, i;
	fi >> n >> k;
	fi >> v[1];
	sc = smax = v[1];
	pc = uc = 1;
	for (i = 2; i <= n; i++)
	{
		fi >> v[i];
		if (sc + v[i] < v[i])
		{
			sc = v[i];
			pc = i;
			uc = i;
		}
		else {
			sc += v[i];
			uc++;
		}
		if (sc > smax)
		{
			smax = sc;
			start = pc;
			ultim = uc;
		}
	}
	if (ultim - start + 1 >= k)
		fo << start << " " << ultim << " " << smax;
	else
	{
		while (ultim - start + 1 < k || smax + v[start - 1] > smax || smax + v[ultim + 1] > smax)
		{
			if (start > 1 && ultim < n)
			{
				if (v[start - 1] > v[ultim + 1])
				{
					start--;
					smax += v[start];
				}
				else
				{
					ultim++;
					smax += v[ultim];
				}
			}
			else if (ultim < n)
			{
				ultim++;
				smax += v[ultim];
			}
			else if (start > 1)
			{
				start--;
				smax += v[start];
			}
		}
		fo << start << " " << ultim << " " << smax;
	}


	return 0;
}