Advertisement
tuki2501

QBSELECT.cpp

Sep 23rd, 2022
552
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.03 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. void chmax(ll &a, ll b) {
  7.     if (a < b) a = b;
  8. }
  9.  
  10. int main() {
  11.     cin.tie(0)->sync_with_stdio(0);
  12.     int n; cin >> n;
  13.     ll ans = LLONG_MIN;
  14.     bool allneg = true;
  15.     vector<vector<ll>> a(n + 1, vector<ll>(4));
  16.     for (int j = 0; j < 4; j++) {
  17.         for (int i = 1; i <= n; i++) {
  18.             cin >> a[i][j];
  19.             ans = max(ans, a[i][j]);
  20.             if (a[i][j] >= 0) allneg = false;
  21.         }
  22.     }
  23.     if (allneg) {
  24.         cout << ans << '\n';
  25.         return 0;
  26.     }
  27.     vector<int> masks;
  28.     for (int mask = 0; mask < (1 << 4); mask++) {
  29.         bool flag = false;
  30.         for (int i = 0; i + 1 < 4; i++) {
  31.             if (((mask >> i) & 1) && ((mask >> (i + 1)) & 1)) {
  32.                 flag = true;
  33.                 break;
  34.             }
  35.         }
  36.         if (!flag) masks.push_back(mask);
  37.     }
  38.     vector<vector<int>> adj(1 << 4);
  39.     for (int i = 0; i + 1 < (int) masks.size(); i++)
  40.     for (int j = i; j < (int) masks.size(); j++) {
  41.         bool flag = false;
  42.         for (int k = 0; k < 4; k++) {
  43.             if (((masks[i] >> k) & 1) && ((masks[j] >> k) & 1)) {
  44.                 flag = true;
  45.                 break;
  46.             }
  47.         }
  48.         if (!flag) {
  49.             adj[masks[i]].push_back(masks[j]);
  50.             adj[masks[j]].push_back(masks[i]);
  51.         }
  52.     }
  53.     vector<vector<ll>> dp(n + 1, vector<ll>(1 << 4));
  54.     for (int i = 1; i <= n; i++) {
  55.         for (auto &mask : masks) {
  56.             ll sum = 0;
  57.             for (int j = 0; j < 4; j++) {
  58.                 if ((mask >> j) & 1) {
  59.                     sum += a[i][j];
  60.                 }
  61.             }
  62.             if (i == 1) {
  63.                 dp[i][mask] = sum;
  64.             }
  65.             else {
  66.                 for (auto &prv_mask : adj[mask]) {
  67.                     chmax(dp[i][mask], dp[i - 1][prv_mask] + sum);
  68.                 }
  69.             }
  70.             if (i == n) chmax(ans, dp[i][mask]);
  71.         }
  72.     }
  73.     cout << ans << '\n';
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement