#1130098 (C++23) No.3322 引っ張りだこ

• 問題: No.3322 引っ張りだこ
• ユーザー: kαmμ
• 提出日時: 2025-10-31 22:11:26
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 12,150 bytes
• コンパイル時間: 3,082 ms
• コンパイル使用メモリ: 285,316 KB
• 実行使用メモリ: 15,936 KB
• 最終ジャッジ日時: 2025-10-31 22:11:35
• 合計ジャッジ時間: 9,298 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

ファイルパターン	結果
other	AC * 5 TLE * 1 -- * 37

ソースコード

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using piii = pair<int, pii>;
using si = set<int>;
using vi = vector<int>;
using vpii = vector<pii>;
using vvi = vector<vector<int>>;
using vvpii = vector<vector<pii>>;

using vb = vector<bool>;

using pli = pair<ll, int>;
using plii = pair<pli, int>;
using vpli = vector<pli>;
using vvpli = vector<vector<pli>>;

using pll = pair<ll, ll>;
using plll = pair<pll, ll>;
using vl = vector<ll>;
using vpll = vector<pll>;
using vvl = vector<vector<ll>>;
using vvpll = vector<vector<pll>>;

using vsi = vector<set<int>>;

using vs = vector<string>;

#define pqueue priority_queue
#define fir first
#define sec second

#define inf 2147483647
#define _inf -2147483648
#define INF (ll)(9223372036854775807)
#define _INF (ll)(-9223372036854775808)

#define Smod 998244353
#define Bmod 1000000007

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define inp_arr(arr, len) rep(__i, len) cin >> arr[__i]
#define in(list, element) (std::find(list, list + sizeof(list) / sizeof(*list), element) != list + sizeof(list) / sizeof(*list))
#define SAlp2int(c) (static_cast<int>(c) - 97)
#define BAlp2int(c) (static_cast<int>(c) - 65)
#define PI (3.14159265)
#define vGet(vec, i) (vec.at(i))
#define sign(f) (f == 0 ? 0 : (f > 0) * 2 - 1)
#define __lcm(a, b) ((a) / __gcd(a, b) * (b))

struct P
{
  P() { P(0, 0); }
  P(int _x, int _y) : x(_x), y(_y) {}
  int x;
  int y;
  bool operator<(const P &other) const { return tie(x, y) < tie(other.x, other.y); }
  P operator+(const P &other) const { return P(x + other.x, y + other.y); }
  P operator-(const P &other) const { return P(x - other.x, y - other.y); }
  P operator*(const int &other) const { return P(x * other, y * other); }
};

using piP = pair<int, P>;
using vP = vector<P>;
using vpiP = vector<piP>;
using vvP = vector<vector<P>>;
using vvpiP = vector<vector<piP>>;

struct modint
{
  modint(int _mod)
  {
    modint(_mod, 0);
  }
  modint(int _mod, ll _val) : mod(_mod)
  {
    if (_val < 0)
      _val = _val % mod + mod;
    if (_val >= mod)
      _val %= mod;
    val = _val;
  }
  int mod;
  int val;

  modint operator+(const modint &other) const { return modint(mod, val + other.val); }
  modint operator-(const modint &other) const { return modint(mod, val - other.val); }
  modint operator*(const modint &other) const { return modint(mod, (ll)val * other.val); }
  modint inv() const { return pow(mod - 2); }
  modint operator/(const modint &other) const { return *this * other.inv(); }
  modint &operator+=(const modint &other) { return *this = *this + other; }
  modint &operator-=(const modint &other) { return *this = *this - other; }
  modint &operator*=(const modint &other) { return *this = *this * other; }
  modint &operator/=(const modint &other) { return *this = *this / other; }

  modint operator+(const int &other) const { return modint(mod, val + other); }
  modint operator-(const int &other) const { return modint(mod, val - other); }
  modint operator*(const int &other) const { return modint(mod, (ll)val * other); }
  modint operator/(const int &other) const { return *this / other; }
  modint &operator+=(const int &other) { return *this = *this + other; }
  modint &operator-=(const int &other) { return *this = *this - other; }
  modint &operator*=(const int &other) { return *this = *this * other; }
  modint &operator/=(const int &other) { return *this = *this / other; }

  modint pow(ll exp) const
  {
    modint res = 1, base = val;
    while (exp)
    {
      if (exp & 1)
        res *= base;
      base *= base;
      exp >>= 1;
    }
    return res;
  }
  friend ostream &operator<<(ostream &os, const modint &m)
  {
    return os << m.val;
  }
};

template <typename _T>
struct bit
{
  bit(int _size) : size(_size + 2), container(_size, 0) {}

  void add(int ind, _T val)
  {
    for (int i = ind; i < size; i += (i & -i))
      container[i] += val;
  }
  _T sumTo(int to)
  {
    _T ans = 0;
    for (int i = to; i > 0; i -= (i & -i))
      ans += container[i];
    return ans;
  }
  _T sum(int from)
  {
    return sum(from, size - 1);
  }
  _T sum(int from, int to)
  {
    return sumTo(to) - sumTo(from - 1);
  }
  int lower_bound(_T w)
  {
    if (w <= 0)
    {
      return 0;
    }
    else
    {
      int ind = 0;
      int r = 1;
      while (r < size)
        r = r << 1;
      for (int len = r; len > 0; len = len >> 1)
      {
        if (ind + len < size && container[ind + len] < w)
        {
          w -= container[ind + len];
          ind += len;
        }
      }
      return ind + 1;
    }
  }
  int size;
  vector<_T> container;
};
template <typename _T>
struct raq_bit
{
  raq_bit(int _size) : bit0(_size), bit1(_size), size(_size + 2) {}

  void add(int l, int r, _T val)
  {
    bit0.add(l, -val * (l - 1));
    bit0.add(r + 1, val * r);
    bit1.add(l, val);
    bit1.add(r + 1, -val);
  }
  _T sumTo(int to)
  {
    return bit0.sumTo(to) + bit1.sumTo(to) * to;
  }
  _T sum(int from)
  {
    return sum(from, size - 1);
  }
  _T sum(int from, int to)
  {
    return sumTo(to) - sumTo(from - 1);
  }
  bit<_T> bit0;
  bit<_T> bit1;
  int size;
};

template <class Monoid, typename _T>
struct segtree
{
  segtree(int _size) : segtree(vector<_T>(_size, Monoid::e), _size) {}
  segtree(vector<_T> &vec, int _size)
  {
    leaves = 1;
    while (_size > leaves)
      leaves <<= 1;
    size = leaves * 2 - 1;
    set_all(vec);
  }
  int size;
  int leaves;
  vector<_T> container;

  void set_all(vector<_T> &vec)
  {
    rep(i, leaves) container[leaves + i] = vec[i];
    rep(i, leaves - 1) update(leaves - 1 - i);
  }

  void update(int i)
  {
    container[i] = Monoid::op(container[2 * i], container[2 * i + 1]);
  }

  void apply(int i, _T &x)
  {
    i += leaves;
    container[i] = _T::op(container[i], x);
    while (i >>= 1)
      update(i);
  }

  void prod(int L, int R)
  {
    _T vl = Monoid::e, vr = Monoid::e;
    L += leaves, R += leaves;
    while (L < R)
    {
      if (L & 1)
        vl = Monoid::op(vl, container[L++]);
      if (R & 1)
        vr = Monoid::op(container[--R], vr);
      L >>= 1, R >>= 1;
    }
    return Monoid::op(vl, vr);
  }

  _T prod_all() { return container[1]; }

  _T get(int i) { return container[i + leaves]; }
};

template <int _size, typename _T = string>
struct trie
{
  _T data;
  bool head = false;
  bool has_child = false;
  trie<_size> *children;
  void make_child()
  {
    children = new trie<_size>[_size];
    has_child = true;
    return;
  }
  _T access(char *S, int deeper)
  {
    if (!deeper)
      return children[SAlp2int(*S)].access(S + 1, deeper - 1);
    return data;
  }
  void add(char *S, int deeper, _T data)
  {
    make_child();
    children[SAlp2int(*S)].add(S + 1, deeper - 1);
    return;
  }
  void add(string S)
  {
    add(S, S.length(), S);
  }
};

struct union_find
{
  union_find(int _size) : nodes(_size), parent(_size)
  {
    rep(i, nodes)
        parent[i] = i;
  }

  int find(int x)
  {
    if (parent[x] == x)
      return x;
    return (parent[x] = find(parent[x]));
  }

  bool unite(int a, int b)
  {
    a = find(a);
    b = find(b);
    if (parent[a] == parent[b])
      return false;
    if (size[a] < size[b])
      swap(a, b);
    parent[b] = a;
    size[a] += size[b];
    return true;
  }

  bool same(int a, int b)
  {
    return (find(a) == find(b));
  }

  int get_size(int x)
  {
    return size[find(x)];
  }

  int nodes;
  vi parent;
  vi size;
};

template <typename _T>
struct Compressor
{
  Compressor(vector<_T> &vec) : size(0)
  {
    unzipped = vec;
    for (_T elem : unzipped)
      zipped[elem] = (size++);
  }
  unordered_map<_T, int> zipped;
  int size;
  vector<_T> unzipped;

  void compress(_T val)
  {
    unzipped.push_back(val);
    zipped[val] = (size++);
  }

  int zip(_T val)
  {
    return zipped[val];
  }

  _T unzip(int x)
  {
    return unzipped[x];
  }
};

struct dir_edges
{
  dir_edges(int _size) : size(_size), container(_size) {}
  vsi container;
  int size;

  void add(int from, int to)
  {
    container[from].insert(to);
  }
  si get(int from)
  {
    return container[from];
  }
};
struct edges
{
  edges(int _size) : size(_size), container(_size) {}
  dir_edges container;
  int size;

  void add(int a, int b)
  {
    container.add(a, b);
    container.add(b, a);
  }
  si get(int from)
  {
    return container.get(from);
  }
};

template <typename _T>
struct wedge
{
  wedge(int _to, _T _weight)
  {
    to = _to;
    weight = _weight;
  }
  int to;
  _T weight;
  bool operator<(const wedge &other) const
  {
    return tie(weight, to) < tie(other.weight, other.to);
  }
};
template <typename _T>
using swe = set<wedge<_T>>;
template <typename _T>
using vswe = vector<swe<_T>>;
using vswei = vswe<int>;

template <typename _T>
struct dijkstra
{
  _T __inf = inf / 2;
  void init()
  {
    rep(i, nodes)
    {
      dist[i] = __inf;
      deted[i] = false;
    }
  }
  void run()
  {
    pqueue<pii, vpii, greater<pii>> que;
    que.emplace(0, start);
    dist[start] = 0;
    prev[start] = -1;
    while (!que.empty())
    {
      pii q = que.top();
      que.pop();
      int n = q.second;
      if (deted[n])
        continue;
      deted[n] = true;
      for (wedge<_T> e : edges[n])
      {
        _T _d = dist[n] + e.weight;
        if (dist[e.to] > _d)
        {
          dist[e.to] = _d;
          prev[e.to] = n;
          que.emplace(_d, e.to);
        }
      }
    }
  }
  dijkstra(vswe<_T> &_edges, int _nodes)
  {
    nodes = _nodes;
    dist.resize(nodes);
    deted.resize(nodes);
    prev.resize(nodes);
    edges = _edges;
    init();
  }
  dijkstra(vswe<_T> &_edges)
  {
    dijkstra(_edges, edges.size());
  }
  dijkstra(int _nodes)
  {
    vector<_T> _v(_nodes);
    dijkstra(_v, _nodes);
  }
  _T getLen(int i)
  {
    return dist[i];
  }
  queue<int> getRoute(int i)
  {
    queue<int> q;
    int n = i;
    while (n != start)
    {
      q.push(n);
      n = prev[n];
    }
    return q;
  }
  vswe<_T> edges;
  int start;
  vector<_T> dist;
  vb deted;
  int nodes;
  vi prev;
};

struct LCS
{
  LCS(string _s1, string _s2) : S1(_s1), S2(_s2)
  {
    s1 = S1.length(), s2 = S2.length();
    len = new int *[s1 + 1];
    rep(i, s1 + 1) len[i] = new int[s2 + 1];
  }
  string S1, S2;
  int s1, s2;

  int **len;
  int calc_len()
  {
    rep(i, s1 + 1) len[i][0] = 0;
    rep(i, s2 + 1) len[0][i] = 0;

    rep(i, s1) rep(j, s2)
    {
      if (S1[i] == S2[j])
        len[i + 1][j + 1] = len[i][j] + 1;
      else
        len[i + 1][j + 1] = max(len[i + 1][j], len[i][j + 1]);
    }
    return len[s2][s1];
  }
  string get(int i1, int i2)
  {
    string ans = "";
    while (i1 > 0 && i2 > 0)
    {
      if (len[i1][i2] == len[i1 - 1][i2])
        i1--;
      else if (len[i1][i2] == len[i1][i2 - 1])
        i2--;
      else
      {
        ans = S1[i1 - 1] + ans;
        i1--;
        i2--;
      }
    }
    return ans;
  }
  string get() { return get(s1, s2); }
};

ll factorial(int n, int r = 1)
{
  ll ans = 1;
  for (int i = r; i <= n; i++)
  {
    ans *= i;
  }
  return ans;
}

ll Conbination(int n, int r)
{
  return factorial(n, r + 1) / factorial(r);
}

void yes(bool o = false)
{
  if (o)
    cout << "Yes";
  else
    cout << "Yes" << endl;
}
void no(bool o = false)
{
  if (o)
    cout << "No";
  else
    cout << "No" << endl;
}
void yn(bool b, bool o = false)
{
  if (b)
    yes(o);
  else
    no(o);
}

string char2str(char c)
{
  string str({c});
  return str;
}

void solve()
{
  int N, K;
  cin >> N >> K;
  int AB[2][N];
  inp_arr(AB[0], N);
  inp_arr(AB[1], N);

  int prev = 0;
  int sw = 0;
  ll ans = 0;
  rep(i, N)
  {
    if (AB[prev][i] < AB[!prev][i])
    {
      sw++;
      prev = !prev;
    }
    ans += AB[prev][i];
  }
  if (sw <= K)
    cout << ans << endl;
  else
  {
    K++;
    ans = 0;
    ll dp[K + 1];
    rep(i, K) dp[i] = 0;
    rep(i, N) for (int j = min(i, K - 1); j >= 0; j--)
    {
      dp[j + 1] = max(dp[j + 1], dp[j] + AB[!(j % 2)][i]);
      dp[j] += AB[j % 2][i];
    }
    rep(i, K) ans = max(ans, dp[i]);
    cout << ans << endl;
  }
}
int main()
{
  int T;
  cin >> T;
  while (T--)
    solve();
  return 0;
}