Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n;
- int a[20];
- int dp[10][1 << 20];
- int bestPairing(int board, int mask) {
- if(board == n + 1) return 0; // base case
- if(dp[board][mask] != -1) {
- return dp[board][mask]; // if ans already found in dp arr the return
- }
- // if ans not already computed, then compute
- int ans = 0;
- for (int i = 0; i < 2 * n; ++i) {
- for (int j = 0; j < 2 * n; ++j) {
- if( (mask & ((1 << i) | (1 << j))) == 0 )
- ans = max(ans, board * abs(a[i] - a[j]) * gcd(a[i], a[j]) + bestPairing(board + 1, mask | (1 << i) | (1 << j)));
- }
- }
- dp[board][mask] = ans; // store ans and then return
- return dp[board][mask];
- }
- int main() {
- cin >> n;
- for (int i = 0; i < 2 * n; ++i) {
- cin >> a[i];
- }
- memset(dp, -1, sizeof dp);
- cout << bestPairing(1, 0) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement