Cod sursa(job #1604054)

Utilizator krityxAdrian Buzea krityx Data 17 februarie 2016 22:05:14
Problema Secventa 2 Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <deque>
#include <algorithm>
#define NMAX 50001
using namespace std;

pair<int, int> AIB[NMAX];

int lIndex(int i)
{
	return (i ^ (i - 1)) & i;
}

void process(int index, int value, int limit)
{
	for (int i = index; i <= limit; i += lIndex(i))
	{
		if (value < AIB[i].second)
		{
			AIB[i] = make_pair(index, value);
		}
	}
}
pair<int, int> query(int index)
{
	int i; 
	pair<int, int> result = make_pair(-1, 1 << 30);
	for (i = index; i > 0; i -= lIndex(i))
	{
		if (AIB[i].second < result.second)
		{
			result.second = AIB[i].second;
			result.first = AIB[i].first;
		}
	}
	return result;
}

int main()
{
	int n, k, v[NMAX], pSum[NMAX], i, smax = - (1<<30), start, end;
	deque<int> d;
	ifstream f("secv2.in");
	f >> n >> k;
	pSum[0] = 0;
	for (i = 1; i <= n; i++)
	{
		f >> v[i];
		pSum[i] = pSum[i - 1] + v[i];
		process(i, pSum[i], n);
	}
	f.close();
	for (i = k; i <= n; i++)
	{
		pair<int, int> min = query(i - k );
		if (pSum[i] - min.second > smax)
		{
			smax = pSum[i] - min.second;
			start = min.first + 1;
			end = i;
		}
	}

	ofstream g("secv2.out");
	g << start << " " << end << " " << smax;
	g.close();
	return 0;
}