Submission #198462

#	Time	Username	Problem	Language	Result	Execution time	Memory
198462		QCFium	Holiday (IOI14_holiday)	C++14	47 / 100	476 ms	7416 KiB

holiday

#include <bits/stdc++.h>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

std::vector<int> a;
int start, d;

struct TopK {
	int k;
	std::multiset<int> upper;
	std::multiset<int> lower;
	int64_t upper_sum = 0;
	TopK (int k) : k(k) {}
	void low_to_up() {
		assert(lower.size());
		auto greatest = std::prev(lower.end());
		upper.insert(*greatest);
		upper_sum += *greatest;
		lower.erase(greatest);
	}
	void up_to_low() {
		assert(upper.size());
		auto lowest = upper.begin();
		upper_sum -= *lowest;
		lower.insert(*lowest);
		upper.erase(lowest);
	}
	void insert(int n) {
		if (!k) {
			lower.insert(n);
			return;
		}
		if ((int) upper.size() == k) {
			auto lowest = upper.begin();
			if (*lowest < n) {
				lower.insert(*lowest);
				upper_sum -= *lowest;
				upper_sum += n;
				upper.erase(lowest);
				upper.insert(n);
			} else lower.insert(n);
		} else upper.insert(n), upper_sum += n;
	}
	void erase(int n) {
		if (upper.size() && *upper.begin() <= n) {
			upper_sum -= n;
			upper.erase(upper.find(n));
			if (lower.size()) low_to_up();
		} else lower.erase(lower.find(n));
	}
	void set_k(int new_k) {
		for (; k < new_k; k++) {
			while (lower.size() && (int) upper.size() <= k) low_to_up();
		}
		for (; k > new_k; k--) {
			while ((int) upper.size() >= k) up_to_low();
		}
		k = new_k;
	}
};
struct RangeSum {
	TopK topk;
	int l = 0;
	int r = 0;
	RangeSum () : topk(d) {}
	void set_lr(int new_l, int new_r) {
		new_r++;
		if (l == r) l = r = new_l;
		while (l > new_l) topk.insert(a[--l]);
		while (r < new_r) topk.insert(a[r++]);
		while (l < new_l) topk.erase(a[l++]);
		while (r > new_r) topk.erase(a[--r]);
		new_r--;
		int move;
		move = new_r - start;
		if (new_l < start) move += new_r - new_l;
		topk.set_k(std::max(0, d - move));
	}
	int64_t sum() { return topk.upper_sum; }
};

RangeSum sum;
std::vector<int64_t> dp;
// [], []
void monotone_minima(int rl, int rr, int ll, int lr) {
	int rm = rl + ((rr - rl) >> 1);
	int64_t max = -1;
	int maxindex = -1;
	for (int i = ll; i <= std::min(lr, rm); i++) {
		sum.set_lr(i, rm);
		int64_t cur = sum.sum();
		if (max < cur) {
			max = cur;
			maxindex = i;
		}
	}
	assert(maxindex != -1);
	dp[rm] = max;
	if (rl < rm) monotone_minima(rl, rm - 1, ll, maxindex);
	if (rm < rr) monotone_minima(rm + 1, rr, maxindex, lr);
}

int64_t solve() {
	int n = a.size();
	dp.assign(n, 0);
	monotone_minima(start, n - 1, 0, start);
	return *std::max_element(dp.begin(), dp.end());
}

long long int findMaxAttraction(int n, int start_, int d_, int attraction[]) {
	a.resize(n);
	for (int i = 0; i < n; i++) a[i] = attraction[i];
	start = start_;
	d = d_;
	
	int64_t res = solve();
	start = n - 1 - start;
	std::reverse(a.begin(), a.end());
	sum = RangeSum();
	res = std::max(res, solve());
	return res;
}

/*
int main() {
	int n = ri();
	int start = ri();
	int d = ri();
	int a[n];
	for (auto &i : a) i = ri();
	std::cout << findMaxAttraction(n, start, d, a) << std::endl;
	
	return 0;
}
//*/

Compilation message (stderr)

holiday.cpp: In function 'int ri()':
holiday.cpp:5:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53