oj.uz

답안 #145371

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145371 2019-08-19T17:47:17 Z faremy 휴가 (IOI14_holiday) C++14
100 / 100
 816 ms 6396 KB 
#include "holiday.h"

#include <algorithm>


const int MAXN = 1e5;
const int LEAVES = 1 << 17;
const int TSIZE = LEAVES << 1;

long long toVisit[MAXN];
int reindex[MAXN];
int corresLeaf[MAXN];

long long visitSum[TSIZE];
int active[TSIZE];

int left, right;


void upd(int node, long long val, long long type)
{
	if (node != 1)
		upd(node >> 1, val, type);
	visitSum[node] += val * type;
	active[node] += type;
}

long long sum(int node, int want)
{
	if (want <= 0)
		return 0;
	if (want >= active[node])
		return visitSum[node];
	if (node < LEAVES)
		return (sum(node * 2, want) + sum(node * 2 + 1, want - active[node * 2]));
	return 0;
}

long long compute(int lleft, int rleft, int lright, int rright, int startCity, int days)
{
	if (lleft == rleft)
		return 0;
	int pos = (lleft + rleft) / 2;

	while (left > pos)
	{
		left--;
		upd(corresLeaf[left], toVisit[left], 1);
	}

	while (left < pos)
	{
		upd(corresLeaf[left], toVisit[left], -1);
		left++;
	}
	
	while (right < lright)
	{
		upd(corresLeaf[right], toVisit[right], 1);
		right++;
	}

	while (right > lright)
	{
		right--;
		upd(corresLeaf[right], toVisit[right], -1);
	}

	int opt = -1; long long weightOpt = -1;
	int used = 2 * (startCity - pos) + (lright - startCity);

	for (int iEnd = lright; iEnd < rright; iEnd++)
	{
		upd(corresLeaf[iEnd], toVisit[iEnd], 1);
		long long weight = sum(1, std::max(0, days - used));
		used++;

		if (weight > weightOpt)
		{
			opt = iEnd;
			weightOpt = weight;
		}
	}

	for (int iEnd = lright; iEnd < rright; iEnd++)
		upd(corresLeaf[iEnd], toVisit[iEnd], -1);
	long long recurs = std::max(compute(lleft, pos, lright, opt + 1, startCity, days), compute(pos + 1, rleft, opt, rright, startCity, days));
	return std::max(weightOpt, recurs);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
	int cities = n, startCity = start, days = d;
	for (int iCity = 0; iCity < cities; iCity++)
	{
		toVisit[iCity] = attraction[iCity];
		reindex[iCity] = iCity;
	}

	std::sort(reindex, reindex + cities, [](int a, int b) { return toVisit[a] > toVisit[b]; });
	for (int iCity = 0; iCity < cities; iCity++)
		corresLeaf[reindex[iCity]] = LEAVES + iCity;
	
	left = startCity; right = startCity;
	long long maxVisit = compute(0, startCity + 1, startCity, cities, startCity, days);
	
	std::reverse(toVisit, toVisit + cities);
	std::reverse(corresLeaf, corresLeaf + cities);
	std::fill_n(visitSum, TSIZE, 0);
	std::fill_n(active, TSIZE, 0);
	startCity = cities - 1 - startCity;

	left = startCity; right = startCity;
	maxVisit = std::max(maxVisit, compute(0, startCity + 1, startCity, cities, startCity, days));
	return maxVisit;

	return 0;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 3448 KB Output is correct
2 Correct 4 ms 3448 KB Output is correct
3 Correct 5 ms 3448 KB Output is correct
4 Correct 4 ms 3320 KB Output is correct
5 Correct 4 ms 3320 KB Output is correct
6 Correct 4 ms 3448 KB Output is correct
7 Correct 4 ms 3448 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 161 ms 5752 KB Output is correct
2 Correct 161 ms 5624 KB Output is correct
3 Correct 162 ms 5496 KB Output is correct
4 Correct 172 ms 5568 KB Output is correct
5 Correct 172 ms 5600 KB Output is correct
6 Correct 48 ms 3960 KB Output is correct
7 Correct 91 ms 4700 KB Output is correct
8 Correct 113 ms 4816 KB Output is correct
9 Correct 35 ms 3960 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 3448 KB Output is correct
2 Correct 9 ms 3448 KB Output is correct
3 Correct 9 ms 3448 KB Output is correct
4 Correct 20 ms 3448 KB Output is correct
5 Correct 18 ms 3448 KB Output is correct
6 Correct 7 ms 3448 KB Output is correct
7 Correct 8 ms 3448 KB Output is correct
8 Correct 8 ms 3448 KB Output is correct
9 Correct 8 ms 3448 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 6160 KB Output is correct
2 Correct 165 ms 6264 KB Output is correct
3 Correct 254 ms 4592 KB Output is correct
4 Correct 17 ms 3448 KB Output is correct
5 Correct 8 ms 3448 KB Output is correct
6 Correct 9 ms 3452 KB Output is correct
7 Correct 9 ms 3448 KB Output is correct
8 Correct 816 ms 6208 KB Output is correct
9 Correct 806 ms 6396 KB Output is correct