QBGAME.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void chmax(ll &a, ll b) {
    if (a < b) a = b;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n;
    ll ans = LLONG_MIN;
    bool allneg = true;
    vector<vector<ll>> a(n + 1, vector<ll>(8));
    for (int j = 0; j < 8; j++) {
        for (int i = 1; i <= n; i++) {
            cin >> a[i][j];
            ans = max(ans, a[i][j]);
            if (a[i][j] >= 0) allneg = false;
        }
    }
    if (allneg) {
        cout << ans << '\n';
        return 0;
    }
    vector<int> masks;
    for (int mask = 0; mask < (1 << 8); mask++) {
        bool flag = false;
        for (int i = 0; i + 1 < 8; i++) {
            if (((mask >> i) & 1) && ((mask >> (i + 1)) & 1)) {
                flag = true;
                break;
            }
        }
        if (!flag) masks.push_back(mask);
    }
    vector<vector<int>> adj(1 << 8);
    for (int i = 0; i + 1 < (int) masks.size(); i++)
    for (int j = i; j < (int) masks.size(); j++) {
        bool flag = false;
        for (int k = 0; k < 8; k++) {
            if (((masks[i] >> k) & 1) && ((masks[j] >> k) & 1)) {
                flag = true;
                break;
            }
        }
        if (!flag) {
            adj[masks[i]].push_back(masks[j]);
            adj[masks[j]].push_back(masks[i]);
        }
    }
    vector<vector<ll>> dp(n + 1, vector<ll>(1 << 8));
    for (int i = 1; i <= n; i++) {
        for (auto &mask : masks) {
            ll sum = 0;
            for (int j = 0; j < 8; j++) {
                if ((mask >> j) & 1) {
                    sum += a[i][j];
                }
            }
            if (i == 1) {
                dp[i][mask] = sum;
            }
            else {
                for (auto &prv_mask : adj[mask]) {
                    chmax(dp[i][mask], dp[i - 1][prv_mask] + sum);
                }
            }
            if (i == n) chmax(ans, dp[i][mask]);
        }
    }
    cout << ans << '\n';
}