DuongNhi99

QBSELECT

Dec 10th, 2020
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 10005;
  5.  
  6. int n;
  7. int64_t a[5][N];
  8. int d[] = {0, 1, 2, 4, 5, 8, 9, 10};
  9. int64_t dp[N][17];
  10. int64_t res = -1e9;
  11.  
  12. int get_bit(int x, int k) {
  13.     return (x >> k) & 1;
  14. }
  15.  
  16. void solve() {
  17.     cin >> n;
  18.     for(int i = 0; i < 4; ++i)
  19.         for(int j = 1; j <= n; ++j) {
  20.             cin >> a[i][j];
  21.             res = max(res, a[i][j]);
  22.         }
  23.  
  24.     if(res < 0) {
  25.         cout << res << '\n';
  26.         return;
  27.     }
  28.  
  29.     for(int j = 1; j <= n; ++j) {
  30.         for(int mask = 0; mask < 8; ++mask) {
  31.             for(int i = 0; i < 4; ++i) {
  32.                 if(get_bit(d[mask], i))
  33.                     dp[j][d[mask]] += a[i][j];
  34.             }
  35.  
  36.             int64_t tmp = -1e8;
  37.             for(int bitmask = 0; bitmask < 8; ++ bitmask) {
  38.                 if((d[mask] | d[bitmask]) == (d[mask] ^ d[bitmask]))
  39.                      tmp = max(tmp, dp[j-1][d[bitmask]]);
  40.             }
  41.  
  42.             dp[j][d[mask]] += tmp;
  43.         }
  44.     }
  45.  
  46.     for(int i = 0; i< 8; ++i)
  47.         res = max(res, dp[n][d[i]]);
  48.     cout << res << '\n';
  49. }
  50.  
  51. int main() {
  52.     //freopen("in.txt", "r", stdin);
  53.     //freopen("QBSELECT.inp", "r", stdin);
  54.     //freopen("QBSELECT.out", "w", stdout);
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(NULL); cout.tie(NULL);
  57.  
  58.     solve();
  59.  
  60.     return 0;
  61. }
  62.  
Advertisement
Add Comment
Please, Sign In to add comment