#include "jelly.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int find_maximum_unique(int X, int Y, std::vector<int> A, std::vector<int> B) {
ll MAX = 1e18;
int N = A.size();
vector<tuple<ll,ll>> S;
for(ll i = 0;i < N;i++) S.emplace_back(A[i],B[i]);
sort(S.begin(),S.end());
for(ll i = 0;i < N;i++) tie(A[i],B[i]) = S[i];
// ABBBAABABXXBXBX
vector<vector<ll>> AB_DP(N + 1,vector<ll>(X + 1,MAX));
//AB_DP[0][0] = 0;
for(ll i = 0;i <= X;i++) AB_DP[0][i] = 0;
for(ll i = 0;i < N;i++){
for(ll j = 0;j <= X;j++) if(AB_DP[i][j] != MAX){
// A
if(j + A[i] <= X) AB_DP[i + 1][j + A[i]] = min(AB_DP[i + 1][j + A[i]],AB_DP[i][j]);
// B
AB_DP[i + 1][j] = min(AB_DP[i + 1][j],AB_DP[i][j] + B[i]);
}
}
vector<ll> B_DP(N + 1,MAX);
B_DP[0] = 0;
ll ans = 0;
for(ll i = N - 1;i >= 0;i--){
for(ll j = 0;j <= N;j++) if(AB_DP[i + 1][X] + B_DP[j] <= Y) ans = max(ans,i + 1 + j);
for(ll j = N - 1;j >= 0;j--) B_DP[j + 1] = min(B_DP[j + 1],B_DP[j] + B[i]);
for(ll j = 0;j <= N;j++) if(AB_DP[i][X] + B_DP[j] <= Y) ans = max(ans,i + j);
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |