Submission #198453

#	Time	Username	Problem	Language	Result	Execution time	Memory
198453		QCFium	Holiday (IOI14_holiday)	C++14	40 / 100	5076 ms	6008 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) {
			assert(upper.count(n));
			upper_sum -= n;
			upper.erase(upper.find(n));
			if (lower.size()) low_to_up();
		} else assert(lower.count(n)), 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 (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) {
		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]);
		int move = (new_r - start - 1);
		if (new_l < start) move += (new_r - new_l - 1);
		topk.set_k(std::max(0, d - move));
	}
	int64_t sum() { return topk.upper_sum; }
};

/*
std::vector<int64_t> dp;
void monotone_minima1(int rl, int rr, int ll, int lr) {
	
}*/

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_;
	
	RangeSum sum;
	int64_t res = 0;
	for (int i = 0; i <= start; i++) {
		for (int j = start + 1; j <= n; j++) {
			sum.set_lr(i, j);
			res = std::max(res, sum.sum());
		}
	}
	
	/*
	start--;
	// go right first
	dp.assign(n + 1, 0);
	monotone_minima1(start + 1, n, 0, j*/
	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 member function 'void TopK::set_k(int)':
holiday.cpp:61:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while (upper.size() >= k) up_to_low();
           ~~~~~~~~~~~~~^~~~
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: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53