Submission #983695

#	Time	Username	Problem	Language	Result	Execution time	Memory
983695		gustavo_d	Jelly Flavours (IOI20_jelly)	C++17	54 / 100	1109 ms	2097152 KiB

jelly

#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;

int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	int n = a.size();

	bool b_eq = true;
	for (int i=0; i<n-1; i++) {
		if (b[i] != b[i+1]) b_eq = false;
	}

	if (!b_eq) {
		vector<vector<vector<int>>> dp(n+1, vector<vector<int>> (x+1, vector<int> (y+1, 0)));
		for (int i=1; i<=n; i++) {
			for (int xi=0; xi<=x; xi++) {
				for (int yi=0; yi<=y; yi++) {
					// não compra e pega o xi ou yi menor
					dp[i][xi][yi] = max(0, dp[i][xi != 0 ? xi-1 : 0][yi]);
					dp[i][xi][yi] = max(dp[i][xi][yi], dp[i][xi][yi != 0 ? yi-1 : 0]);
					// não compra o i
					dp[i][xi][yi] = max(dp[i][xi][yi], dp[i-1][xi][yi]);
					// compra na a
					if (xi >= a[i-1]) dp[i][xi][yi] = max(dp[i][xi][yi], dp[i-1][xi-a[i-1]][yi] + 1);
					// compra na b
					if (yi >= b[i-1]) dp[i][xi][yi] = max(dp[i][xi][yi], dp[i-1][xi][yi-b[i-1]] + 1);
				}
			}
		}
		return dp[n][x][y];
	} else {
		int cnt = 0, i=0;
		sort(a.begin(), a.end());
		for (; i<n; i++, cnt++) { // acha primeiro que não pode comprar
			if (x < a[i]) break;
			x -= a[i];
		}
		for (; i<n; i++, cnt++) {
			if (y<b[i]) break;
			y-=b[i];
		}

		return cnt;
	}
}

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