結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー areik
提出日時 2025-10-31 22:53:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,761 bytes
コンパイル時間 4,065 ms
コンパイル使用メモリ 257,952 KB
実行使用メモリ 40,288 KB
最終ジャッジ日時 2025-10-31 22:53:52
合計ジャッジ時間 28,600 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using i32 = int;
using i64 = long long;
using i128 = __int128_t;
using p2 = pair<i64, i64>;
using el = tuple<i64, i64, i64>;
using f64 = long double;
using mint = atcoder::modint998244353;


void _main();
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(18);
  _main();
}

i64 pow(i64 a, i64 n) {
  i64 res = 1;
  i64 x = a;
  while (n > 0) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}
vector<i64> maxplusconvolution(vector<i64> &a, vector<i64> &b, i64 op) {
  i64 idx = 0, jdx = 0;
  vector<i64> c(a.size() + b.size() - 1, -1e18);
  c[0] = max(c[0], a[0] + b[0]);
  for (i64 i = 1; i < a.size() + b.size() - 1; i++) {
    if (jdx >= b.size() || (idx < a.size() && a[idx + 1] + b[jdx] >= a[idx] + b[jdx + 1])) {
      c[i] = max(c[i], a[idx + 1] + b[jdx]);
      idx++;
    } else {
      c[i] = max(c[i], a[idx] + b[jdx + 1]);
      jdx++;
    }
  }
  if (op) {
    vector<i64> nc(c.size() + 1, -1e18);
    for (i64 i = 1; i <= c.size(); i++) nc[i] = c[i - 1];
    return nc;
  }
  return c;
}
i64 a[200000], b[200000];
vector<vector<i64>> solve(i64 l, i64 r) {
  if (l + 1 == r) {
    vector<vector<i64>> res(4, vector<i64>(2, -1e18));
    for (i64 i = 0; i < 4; i++) {
      i64 x = __builtin_popcountll(i);
      i64 y = 2 - x;
      x /= 2, y /= 2;
      res[i][x] = max(res[i][x], a[l]);
      res[i][y] = max(res[i][y], b[l]);
      for (i64 j = 1; j < 2; j++) res[i][j] = max(res[i][j], res[i][j - 1]);
    }
    return res;
  }
  i64 mid = (l + r) / 2;
  vector<vector<i64>> a = solve(l, mid);
  vector<vector<i64>> b = solve(mid, r);
  vector<vector<i64>> res(4);
  for (i64 i = 0; i < 4; i++) {
    for (i64 j = 0; j < 4; j++) {
      if ((i >> 1 & 1) != (j >> 0 & 1)) continue;
      i64 op = 0;
      if ((i >> 0 & 1) != (i >> 1 & 1) && (j >> 0 & 1) != (j >> 1 & 1)) op = 1;
      vector<i64> c = maxplusconvolution(a[i], b[j], op);
      i64 ni = (i & 1) + (j & 2);
      while (res[ni].size() < c.size()) res[ni].push_back(-1e18);
      for (i64 k = 0; k < c.size(); k++) {
        res[ni][k] = max(res[ni][k], c[k]);
      }
    }
  }
  return res;
}
void _main() {
  i64 ttt;
  cin >> ttt;
  for (;ttt--;) {
    i64 n, k;
    cin >> n >> k;
    for (i64 i = 0; i < n; i++) {
      cin >> a[i];
    }
    for (i64 i = 0; i < n; i++) {
      cin >> b[i];
    }
    vector<vector<i64>> res = solve(0, n);
    i64 ans = 0;
    for (i64 ni = 0; ni < 4; ni++) {
      if (ni >> 0 & 1) continue;
      for (i64 i = 0; i < res[ni].size(); i++) {
        i64 ti = i * 2;
        if ((ni >> 0 & 1) != (ni >> 1 & 1)) ti++;
        if (ti <= k) ans = max(ans, res[ni][i]);
      }
    }
    cout << ans << "\n";
  }
}
0