제출 #434161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
434161		krist7599555	Jelly Flavours (IOI20_jelly)	C++17	100 / 100	124 ms	452 KiB

jelly

#include <algorithm>
#include <cassert>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <tuple>
typedef std::vector<int> Vec;
typedef std::pair<int, int> Pii;
#define rep(i,a,b) for(auto i = a; i != b; ++i)
 
struct Data {
	int jelly_count, remain_b;
	Data(int cnt, int rem): jelly_count(cnt), remain_b(rem) {}
	Data increase_jelly_count() {return {jelly_count+1, remain_b};}
	Data buy_b(int cost) { return {jelly_count+1, remain_b - cost};}
	bool operator < (const Data& o) const {
		return std::tie(jelly_count, remain_b) < std::tie(o.jelly_count, o.remain_b);
	}
};
 
int find_maximum_unique(int x_total, int y_total, std::vector<int> an, std::vector<int> bn) {
	assert(an.size() == bn.size() and an.size() <= 2e3);
	std::vector<Data> dp(x_total+1, Data(0, 0)); // dp[i] = how many jelly count can do when `remain x` == i
	dp[x_total] = Data(0, y_total); // dp[remain_a=max_x] = { jelly_count: 0, remain_b: max_b }
 
	std::vector<int> ord(an.size()); // ord = sorted index by `b`
	std::iota(ord.begin(), ord.end(), 0); // 0 1 2 3 4 5 6 7
	std::sort(ord.begin(), ord.end(), [&](int u, int v){ return bn[u] < bn[v]; });

	for (int i : ord) {
		int curr_a = an[i]; // a = ? ? ? ? ?
		int curr_b = bn[i]; // b = 1 2 3 4 5 
		for(int remain_a = 0; remain_a <= x_total; ++remain_a) {
			dp[remain_a] = std::max({
				// case 1: not neither buy from `a` or `b`
				dp[remain_a],
				// case 2: buy from `b` greedy
				//   same dp[remain_a] but reduce remain_b
				curr_b <= dp[remain_a].remain_b 
					? dp[remain_a].buy_b(curr_b) // greedy by `b` if possible
					: dp[remain_a],
				// case 3: buy from `a` dynamic programing
				//   reduce from `remain_a + curr_a` to `remain_a`
				curr_a + remain_a <= x_total
					? dp[remain_a + curr_a].increase_jelly_count() // dynamic programming on `a` 
					: dp[remain_a]
			});
		}
	}
	return std::max_element(dp.begin(), dp.end())->jelly_count;
}


#ifdef KRIST_LOCAL

inline int input() { int i; std::cin >> i; return i; }
int main() {
	assert(2 == find_maximum_unique(2, 3, Vec({2, 1, 4}), Vec({2, 3, 2})));
	assert(4 == find_maximum_unique(6, 12, Vec({5, 1, 5, 6, 3}), Vec({3, 5, 4, 6, 7})));
}

#endif

• Subtask 1: 11 / 11
• Subtask 2: 24 / 24
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 14 / 14
• Subtask 6: 32 / 32