Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int main()
- {
- int n; cin >> n;
- ll a[n], b[n];
- for(int i = 0; i < n; i++)
- cin >> a[i];
- for(int i = 0; i < n; i++)
- cin >> b[i];
- //initialise the dp array
- ll dp[1 << n];
- for(int mask = 0; mask < (1 << n); mask++)
- dp[mask] = INT_MIN;
- dp[0] = 0;
- for(int mask = 0; mask < (1 << n); mask++)
- {
- int len = __builtin_popcount(mask);
- //claiming that 'bit' will be the index at position len and use optimal
- //answer for the previous part, as answer for previous part is independent
- //of the value we are placing here. The only thing which changes is the indexes
- //which are available with us, and to keep it's track we are using bitmasks.
- for(int bit = 0; bit < n; bit++)
- if(mask & (1 << bit))
- {
- //switch current bit off to get the previous mask
- int nmask = mask ^ (1 << bit);
- dp[mask] = max(dp[mask], a[bit] * b[len - 1] + dp[nmask]);
- }
- }
- int full_mask = (1 << n) - 1;
- cout << dp[full_mask];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
