結果

問題 No.3322 引っ張りだこ
コンテスト
ユーザー のらら
提出日時 2025-10-05 22:45:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 551 ms / 2,000 ms
コード長 3,074 bytes
コンパイル時間 3,261 ms
コンパイル使用メモリ 181,632 KB
実行使用メモリ 23,744 KB
最終ジャッジ日時 2025-10-31 20:32:45
合計ジャッジ時間 25,152 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

//分割統治法(O(NlogN))
//A→Bへの変更回数で管理する
#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
const long long INF = 1000000000000000000;
//#define endl "\n";
ll N, K, A[200009], B[200009];

//凸性を期待して右下へ探索するO(N)
//雑な実装。ダメならmonotone minimaかSMAWK algorithmを実装する
void merge(int i0, int i1, int j0, int j1, vector<ll> &a, vector<ll> &b, vector<ll> &ret){
  int posa = 0, posb = 0;
  int tasu = ((i1 == 0 && j0 == 1) ? 1: 0);
  ret[posa + posb + tasu] = max(ret[posa + posb + tasu], a[posa] + b[posb]);
  while(1){
    if(posa + 1 < (int)a.size() && posb + 1 < (int)b.size()){
      if(a[posa + 1] + b[posb] >= a[posa] + b[posb + 1]){
        ret[posa + posb + 1 + tasu] = max(ret[posa + posb + 1 + tasu], a[posa + 1] + b[posb]);
        posa++;
        continue;
      }else{
        ret[posa + posb + 1 + tasu] = max(ret[posa + posb + 1 + tasu], a[posa] + b[posb + 1]);
        posb++;
        continue;
      }
    }
    if(posa + 1 < (int)a.size()){
      ret[posa + posb + 1 + tasu] = max(ret[posa + posb + 1 + tasu], a[posa + 1] + b[posb]);
      posa++;
      continue;
    }
    if(posb + 1 < (int)b.size()){
      ret[posa + posb + 1 + tasu] = max(ret[posa + posb + 1 + tasu], a[posa] + b[posb + 1]);
      posb++;
      continue;
    }
    break;
  }
}

//o(NM)
/*void merge(int i0, int i1, int j0, int j1, vector<ll> &a, vector<ll> &b, vector<ll> &ret){
  int tasu = (i1 != j0 ? 1: 0);
  for(int i = 0; i < (int)a.size(); i++){
    for(int j = 0; j < (int)b.size(); j++){
      ret[i + j + tasu] = max(ret[i + j + tasu], a[i] + b[j]);
    }
  }
}*/

vector<vector<ll>> f(int l, int r){
  if(l == r){
    vector<vector<ll>> ret = {{A[l]}, {-INF}, {-INF}, {B[l]}};
    return ret;
  }
  auto ret1 = f(l, (l + r) / 2);
  auto ret2 = f((l + r) / 2 + 1, r);
  int n = ret1[0].size();
  int m = ret2[0].size();
  vector<vector<ll>> ret(4, vector<ll>(n + m, -INF));
  for(int i0 = 0; i0 < 2; i0++){
    for(int i1 = 0; i1 < 2; i1++){
      for(int j0 = 0; j0 < 2; j0++){
        for(int j1 = 0; j1 < 2; j1++){
          merge(i0, i1, j0, j1, ret1[i0 * 2 + i1], ret2[j0 * 2 + j1], ret[i0 * 2 + j1]);
        }
      }
    }
  }
  /*確認用*/
  /*cout << l << " " << r << endl;
  for(int i0 = 0; i0 < 2; i0++){
    for(int i1 = 0; i1 < 2; i1++){
      for(int k = 0; k < n + m; k++) cout << ret[i0 * 2 + i1][k] << " ";
      cout << endl;
    }
  }*/
  return ret;
} 

int main(){
  ll Q;
  cin >> Q;
  for(int q = 1; q <= Q; q++){
    ll N, K;
    cin >> N >> K;
    for(ll i = 0; i < N; i++) cin >> A[i];
    for(ll i = 0; i < N; i++) cin >> B[i];
    auto ret = f(0, N - 1);
    ll ans = -INF;
    for(int k = 0; k <= K / 2; k++) ans = max(ans, ret[0][k]);
    for(int k = 0; k <= (K + 1) / 2; k++) ans = max(ans, ret[1][k]);
    for(int k = 0; k <= K / 2 - 1; k++) ans = max(ans, ret[2][k]);
    for(int k = 0; k <= (K + 1) / 2 - 1; k++) ans = max(ans, ret[3][k]);
    cout << ans << endl;
  }
  return 0;
}
0