Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
This solution works in O(n*log(k)) time. Enjoy ;)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define xx << "\n"
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,k;
cin >> n >> k;
int ind[n], prof[n];
for(int i = 0; i < n; i++)
cin >> ind[i];
for(int i = 0; i < n; i++)
cin >> prof[i];
ll ans = 0;
ll x = k;
while(true) {
ll currp = 0;
//cout << x << " : ";
for(int i = 0; i < n; i++) {
if( (ind[i]|x) == x ) {
currp += prof[i];
cout << prof[i] << " ";
}
}
ans = max(ans, currp);
ll f0 = -1;
for(int b = 0; b < 30; b++) {
if((x & (1<<b)) == 0) {
f0 = b;
break;
}
}
if(f0 == -1 || (1<<f0) > x) break;
else x -= (1<<f0);
}
cout << ans xx;
return 0;
}
Entering edit mode
binary Search Approach - TC - O(NlogN*30) bool check(int mid, vector&pre, vector> &arr, int &sum, int k){ int oro = 0; int demo_k = 0; for(int i = 0; i<31; i++){ if(arr[mid-1][i] > 0){ demo_k += (1<0) temp += (1<0; } void solve() { int n, k; cin>>n>>k; vectora(n), p(n); for(int i = 0; i>a[i]; for(int i = 0; i>p[i]; vector> arr(n, vector(31, 0)); for(int i = 0; ipre(n); pre[0] = p[0]; for(int i = 1; i
Entering edit mode
Dynamic Programming:-
Memoisation:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
class Solution {
public:
ll solve(int n, int k, vector<int>& indicators, vector<int>& profit, ll temp, int index, vector<vector<ll>>& dp) {
if (temp > k || index >= n) {
return 0;
}
if (dp[index][temp] != -1) {
return dp[index][temp];
}
ll maxProfit = 0;
ll not_take = solve(n, k, indicators, profit, temp, index + 1, dp);
ll take = 0;
if ((temp | indicators[index]) <= k) {
take = profit[index] + solve(n, k, indicators, profit, temp | indicators[index], index + 1, dp);
}
maxProfit = max(not_take, take);
return dp[index][temp] = maxProfit;
}
ll maxProfit(int n, int k, vector<int>& indicators, vector<int>& profit) {
vector<vector<ll>> dp(n, vector<ll>(k + 1, -1));
ll ans = solve(n, k, indicators, profit, 0, 0, dp);
return ans;
}
};
void solve() {
int n1;
cin >> n1;
vector<int> indicators(n1);
for (int i = 0; i < n1; i++) {
cin >> indicators[i];
}
int n2;
cin >> n2;
vector<int> profit(n2);
for (int i = 0; i < n2; i++) {
cin >> profit[i];
}
int k;
cin >> k;
Solution obj;
cout << obj.maxProfit(n1, k, indicators, profit) << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Tabulation:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
class Solution {
public:
ll maxProfit(int n, int k, vector<int>& indicators, vector<int>& profit) {
vector<vector<ll>> dp(n+1, vector<ll>(k + 2, -1));
for(ll j = 0; j < k+2; j++){
dp[n][j] = 0;
}
for(ll i = 0; i < n+1; i++){
dp[i][k+1] = 0;
}
for(ll index = n-1; index >= 0; index--){
for(ll temp = k; temp >= 0; temp--){
ll maxProfit = 0;
ll not_take = dp[index+1][temp];
ll take = 0;
if ((temp | indicators[index]) <= k) {
take = profit[index] + dp[index+1][temp | indicators[index]];
}
maxProfit = max(not_take, take);
dp[index][temp] = maxProfit;
}
}
return dp[0][0];
}
};
void solve() {
int n1;
cin >> n1;
vector<int> indicators(n1);
for (int i = 0; i < n1; i++) {
cin >> indicators[i];
}
int n2;
cin >> n2;
vector<int> profit(n2);
for (int i = 0; i < n2; i++) {
cin >> profit[i];
}
int k;
cin >> k;
Solution obj;
cout << obj.maxProfit(n1, k, indicators, profit) << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Loading Similar Posts
This can be done in O(N*30*30) using bit representations for each number
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin>>n>>k;
vector<int>indicators(n, 0);
vector<int>profit(n, 0);
for(int i = 0 ; i < n ; i ++)
{
cin>>indicators[i];
}
map<int, string>binary;
string s = "";
for(int i = 0 ; i < indicators.size() ; i++)
{
int x = indicators[i];
s = "";
for(int j = 0 ; j < 31 ; j++)
{
if((x&(1<<j))>0)
{
s+='1';
}else
{
s+='0';
}
}
reverse(s.begin(), s.end());
binary[x] = s;
}
s = "";
for(int j = 0 ; j < 31 ; j++)
{
if((k&(1<<j))>0)
{
s+='1';
}else
{
s+='0';
}
}
reverse(s.begin(), s.end());
binary[k] = s;
for(int i = 0 ; i < n ; i ++)
{
cin>>profit[i];
}
int ans = 0;
s = binary[k];
for(int i = 0 ; i < s.length() ; i++)
{
int currans = 0;
for(int j = 0 ; j < n ; j ++)
{
bool cantake = true;
string s2 = binary[indicators[j]];
//cout<<indicators[j]<<" "<<s2<<" "<<endl;
for(int l = 0 ; l < s.length() ; l++)
{
if(s[l]=='1' && s2[l]=='0' && l != i)
{
break;
} else if(s[l]=='0' && s2[l]=='1')
{
//cout<<l<<endl;
cantake = false;
break;
}else if (s[l]=='1' && s2[l]=='1' && l == i)
{
//cout<<l<<endl;
cantake = false;
break;
}
}
if(cantake)
{
currans+=profit[j];
}
}
ans = max(ans, currans);
}
cout<<ans<<endl;
}
does this code works for all test cases?
Can we use binary search
Yes I think so