제출 #1317761

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317761		nagorn_ph	Jelly Flavours (IOI20_jelly)	C++20	0 / 100	992 ms	2162688 KiB

jelly

#include <bits/stdc++.h>
#include "jelly.h"

using namespace std;

int find_maximum_unique(int x, int y, vector<int> a, vector<int> b) {
	int n = a.size();
	reverse(a.begin(), a.end()); a.emplace_back(0); reverse(a.begin(), a.end());
	reverse(b.begin(), b.end()); b.emplace_back(0); reverse(b.begin(), b.end());
	int dp[n + 1][x + 1][y + 1]; memset(dp, 0, sizeof dp);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= x; j++) {
			for (int k = 1; k <= y; k++) {
				if (j >= a[i]) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a[i]][k] + 1);
				if (k >= b[i]) dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - b[i]] + 1);
				if (j < a[i] && k < b[i]) {
					dp[i][j][k] = max({dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]});
				}
			}
		}
	}
	return dp[n][x][y];
}

/*
sub 1-2: constraints
dp[i][j][k] = max ans when we used i at a, j at b, checked up to k
answer is at dp[x][y][n]

sub 3: cannot buy from b (only from a)
greedy stupid

sub 4: b is all equal
greedy stupid again

sub 5: a and b are same

*/

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