oj.uz

Submission #198466

# Submission time Handle Problem Language Result Execution time Memory
198466 2020-01-26T07:00:38 Z QCFium Holiday (IOI14_holiday) C++14
100 / 100
 2043 ms 6824 KB 
#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() {
		if (topk.upper.size()) return topk.upper_sum;
		else return -1000000000000000000;
	}
};

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, std::min(n - 1, start + d - 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();
	
	return 0;
}
//*/

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 256 KB Output is correct
7 Correct 5 ms 256 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 6648 KB Output is correct
2 Correct 135 ms 6520 KB Output is correct
3 Correct 134 ms 6520 KB Output is correct
4 Correct 140 ms 6520 KB Output is correct
5 Correct 352 ms 6168 KB Output is correct
6 Correct 65 ms 2040 KB Output is correct
7 Correct 149 ms 3576 KB Output is correct
8 Correct 228 ms 4216 KB Output is correct
9 Correct 44 ms 1528 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 504 KB Output is correct
2 Correct 8 ms 504 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 25 ms 504 KB Output is correct
5 Correct 24 ms 504 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 10 ms 376 KB Output is correct
8 Correct 11 ms 376 KB Output is correct
9 Correct 12 ms 376 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 6520 KB Output is correct
2 Correct 175 ms 6824 KB Output is correct
3 Correct 457 ms 2680 KB Output is correct
4 Correct 31 ms 504 KB Output is correct
5 Correct 11 ms 376 KB Output is correct
6 Correct 11 ms 376 KB Output is correct
7 Correct 11 ms 376 KB Output is correct
8 Correct 2043 ms 6412 KB Output is correct
9 Correct 1940 ms 6372 KB Output is correct