Submission #1318008

#TimeUsernameProblemLanguageResultExecution timeMemory
1318008nagorn_phJelly Flavours (IOI20_jelly)C++20
14 / 100
26 ms480 KiB
#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());
	vector <pair <int, int>> v;
	for (int i = 1; i <= n; i++) {
		v.emplace_back(a[i], b[i]);
	}
	sort(v.begin(), v.end());
	sort(a.begin(), a.end());
	bool dp[10005] = {0}; dp[0] = true;
	int sum = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		sum += a[i];
		for (int j = 10000; j >= a[i]; j--) {
			dp[j] |= dp[j - a[i]];
			if (dp[j] && dp[j] <= x && sum - dp[j] <= y) {
				ans = i;
			}
		}
		for (int j = 10000; j >= 0; j--) {
			if (dp[j] && j <= x && (sum - j) <= y) {
				ans = i;
				break;
			}
		}
	}
	return ans;
}

/*
sub 1-2 , 3: constraints , y = 0
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 4: b is all equal
greedy stupid again

sub 5: a and b are same
knapsack, if can separate into two piles then ok

*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...