//generated by ChatGPT #include using namespace std; using int64 = long long; constexpr int DEFAULT_K = 1000; /* 候補集合を作る。 1. 列の中央に近い位置を K 個 2. 値が大きい位置を K 個 添字は 1-indexed。 */ vector buildCandidates( const vector& values, int K ) { int n = static_cast(values.size()) - 1; vector selected(n + 1, false); vector order(n); iota(order.begin(), order.end(), 1); // 中央との距離は |2*i - (n+1)| で比較できる。 sort(order.begin(), order.end(), [&](int i, int j) { int64 distI = abs(2LL * i - (n + 1LL)); int64 distJ = abs(2LL * j - (n + 1LL)); if (distI != distJ) return distI < distJ; return i < j; }); for (int t = 0; t < min(K, n); ++t) { selected[order[t]] = true; } // 単体の値が大きい位置を選ぶ。 sort(order.begin(), order.end(), [&](int i, int j) { if (values[i] != values[j]) { return values[i] > values[j]; } return i < j; }); for (int t = 0; t < min(K, n); ++t) { selected[order[t]] = true; } vector candidates; candidates.reserve(min(n, 2 * K)); for (int i = 1; i <= n; ++i) { if (selected[i]) { candidates.push_back(i); } } return candidates; } int main(int argc, char* argv[]) { ios::sync_with_stdio(false); cin.tie(nullptr); /* ローカル実行時には ./main 500 のようにして K を変更できる。 引数を指定しなければ K=1000。 */ int K = DEFAULT_K; if (argc >= 2) { K = stoi(argv[1]); } int N, M; cin >> N >> M; vector A(N + 1), B(M + 1); vector C(N + 1), D(M + 1); for (int i = 1; i <= N; ++i) cin >> A[i]; for (int j = 1; j <= M; ++j) cin >> B[j]; for (int i = 1; i <= N; ++i) cin >> C[i]; for (int j = 1; j <= M; ++j) cin >> D[j]; vector prefixA(N + 1, 0); vector prefixB(M + 1, 0); for (int i = 1; i <= N; ++i) { prefixA[i] = prefixA[i - 1] + A[i]; } for (int j = 1; j <= M; ++j) { prefixB[j] = prefixB[j - 1] + B[j]; } vector candidatesA = buildCandidates(A, K); vector candidatesB = buildCandidates(B, K); vector selectedA(N + 1, false); vector selectedB(M + 1, false); for (int i : candidatesA) selectedA[i] = true; for (int j : candidatesB) selectedB[j] = true; const int maxColor = N + M; vector> positionsA(maxColor + 1); vector> positionsB(maxColor + 1); for (int i = 1; i <= N; ++i) { positionsA[C[i]].push_back(i); } for (int j = 1; j <= M; ++j) { positionsB[D[j]].push_back(j); } auto rangeSumA = [&](int left, int right) -> int64 { return prefixA[right] - prefixA[left - 1]; }; auto rangeSumB = [&](int left, int right) -> int64 { return prefixB[right] - prefixB[left - 1]; }; auto calculateScore = [&](int i, int j) -> int64 { int radius = min({ i - 1, N - i, j - 1, M - j }); return rangeSumA(i - radius, i + radius) + rangeSumB(j - radius, j + radius); }; int64 answer = -1; /* A 側の候補中心と、B 側の同色中心をすべて組み合わせる。 */ for (int i : candidatesA) { int color = C[i]; for (int j : positionsB[color]) { answer = max(answer, calculateScore(i, j)); } } /* B 側の候補中心と、A 側の同色中心をすべて組み合わせる。 A 側も候補である組は上で計算済みなので除外する。 これは答えには影響せず、重複計算だけを減らす。 */ for (int j : candidatesB) { int color = D[j]; for (int i : positionsA[color]) { if (selectedA[i]) continue; answer = max(answer, calculateScore(i, j)); } } cout << answer << '\n'; }