View Code of Problem 1093

#ifndef HEAD
#include <stdio.h>
#include <vector>
#include <math.h>
#include <string.h>
#include <string>
#include <iostream>
#include <queue>
#include <list>
#include <algorithm>
#include <stack>
#include <map>

using namespace std;
#endif // !HEAD

struct MUFA
{
	int score;
	int aid;
};

int curaids[2][100001];
MUFA mufas[100001];

int mufscomp(const void* a1, const void* a2)
{
	return ((MUFA*)a1)->score - ((MUFA*)a2)->score;
}

int main()
{
#ifdef _DEBUG
	freopen("d:\\in.txt", "r", stdin);
#endif
	int N, C, F;
	memset(curaids, 0, sizeof(curaids));
	scanf("%d %d %d\n", &N, &C, &F);
	for (size_t i = 0; i < C; i++)
	{
		scanf("%d %d\n", &mufas[i].score, &mufas[i].aid);
	}
	qsort(mufas, C, sizeof(MUFA), mufscomp);
	int start = N / 2;
	int end = C - start - 1;
	priority_queue<int, vector<int>> aids,aids1;
	int curaid = 0;
	for (int i = C - 1; i > end;i--)
	{
		curaid += mufas[i].aid;
		aids.push(mufas[i].aid);
	}
	curaids[0][end] = curaid;
	for (int i = end -1; i >= start; i--)
	{
		if (mufas[i + 1].aid < aids.top())
		{
			curaids[0][i] = curaids[0][i + 1] - aids.top() + mufas[i + 1].aid;
			aids.pop();
			aids.push(mufas[i + 1].aid);
		}
		else
			curaids[0][i] = curaids[0][i + 1];
	}

	curaid = 0;
	for (int i = 0; i < start;i++)
	{
		curaid += mufas[i].aid;
		aids1.push(mufas[i].aid);
	}
	curaids[1][start] = curaid;
	for (int i = start + 1; i <= end;i++)
	{
		if (mufas[i-1].aid < aids1.top())
		{
			curaids[1][i] = curaids[1][i - 1] - aids1.top() + mufas[i - 1].aid;
			aids1.pop();
			aids1.push(mufas[i - 1].aid);
		}
		else
		{
			curaids[1][i] = curaids[1][i - 1];
		}
	}

	int res = -1;
	for (int i = end; i >= start;i--)
	{
		if (mufas[i].aid + curaids[0][i] + curaids[1][i] <= F)
		{
			res = mufas[i].score;
			break;
		}
	}
	printf("%d\n", res);
	return 0;
}
/*
F:\temp\16139847.54864\Main.cc: In function 'int main()':
F:\temp\16139847.54864\Main.cc:47: error: '>>' should be '> >' within a nested template argument list
*/