#1010506 (C++17) No.2889 Rusk

提出ソース

結果

問題	No.2889 Rusk
ユーザー	wai4u
提出日時	2024-09-14 01:40:16
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	106 ms / 2,000 ms
コード長	10,333 bytes
コンパイル時間	3,283 ms
コンパイル使用メモリ	228,396 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-14 01:40:25
合計ジャッジ時間	8,236 ms
ジャッジサーバーID （参考情報）	judge6 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,940 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	2 ms 6,940 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	5 ms 6,944 KB
testcase_15	AC	18 ms 6,940 KB
testcase_16	AC	43 ms 6,940 KB
testcase_17	AC	13 ms 6,940 KB
testcase_18	AC	37 ms 6,944 KB
testcase_19	AC	70 ms 6,940 KB
testcase_20	AC	84 ms 6,940 KB
testcase_21	AC	70 ms 6,944 KB
testcase_22	AC	60 ms 6,940 KB
testcase_23	AC	48 ms 6,940 KB
testcase_24	AC	84 ms 6,944 KB
testcase_25	AC	47 ms 6,940 KB
testcase_26	AC	68 ms 6,940 KB
testcase_27	AC	87 ms 6,940 KB
testcase_28	AC	53 ms 6,940 KB
testcase_29	AC	54 ms 6,940 KB
testcase_30	AC	53 ms 6,940 KB
testcase_31	AC	87 ms 6,940 KB
testcase_32	AC	38 ms 6,944 KB
testcase_33	AC	12 ms 6,944 KB
testcase_34	AC	101 ms 6,944 KB
testcase_35	AC	103 ms 6,940 KB
testcase_36	AC	101 ms 6,944 KB
testcase_37	AC	101 ms 6,940 KB
testcase_38	AC	101 ms 6,944 KB
testcase_39	AC	60 ms 6,940 KB
testcase_40	AC	47 ms 6,940 KB
testcase_41	AC	62 ms 6,940 KB
testcase_42	AC	45 ms 6,940 KB
testcase_43	AC	22 ms 6,944 KB
testcase_44	AC	56 ms 6,940 KB
testcase_45	AC	43 ms 6,940 KB
testcase_46	AC	13 ms 6,940 KB
testcase_47	AC	24 ms 6,940 KB
testcase_48	AC	50 ms 6,940 KB
testcase_49	AC	2 ms 6,944 KB
testcase_50	AC	2 ms 6,940 KB
testcase_51	AC	2 ms 6,940 KB
testcase_52	AC	2 ms 6,944 KB
testcase_53	AC	2 ms 6,940 KB
testcase_54	AC	106 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <set>
using namespace std;
#include <vector>
using std::vector;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
using vvvc = vc<vvc<T>>;
template <class T>
using vvvvc = vc<vvvc<T>>;
#define VC(T, a, ...) auto a = vector<T>(__VA_ARGS__)
#define VVC(T, a, n, ...) \
  auto a = vector(n, vector<T>(__VA_ARGS__));
#define VVVC(T, a, n, m, ...) \
  auto a = vector(n, vector(m, vector<T>(__VA_ARGS__)));
#define VVVVC(T, a, n, m, l, ...) \
  auto a = \
    vector(n, vector(m, vector(l, vector<T>(__VA_ARGS__))));
#define be begin()
#define en end()
#define all(a) (a).be, (a).en
#define rbe rbegin()
#define ren rend()
#define allr(a) a.rbe, a.ren
#include <algorithm>
using std::sort;
template<class A>
void sort(A& a) { sort(all(a)); }
#include <algorithm>
using std::sort;
template<class A>
void sortr(A& a) { sort(allr(a)); }
#include <algorithm>
using std::reverse;
template<class A>
void reverse(A& a) { reverse(all(a)); }
#define eval_0(a, ...) a
#define eval_1(a, b, ...) b
#define eval_2(a, b, c, ...) c
#define eval_3(a, b, c, d, ...) d
#define eval_4(a, b, c, d, e, ...) e
#define eval_5(a, b, c, d, e, f, ...) f
#define eval_6(a, b, c, d, e, f, g, ...) g
#define iter_1(a, A) for (auto&& a : A)
#define iter_2(a, b, A) for (auto&& [a, b] : A)
#define iter_3(a, b, c, A) for (auto&& [a, b, c] : A)
#define iter_4(a, b, c, d, A) for (auto&& [a, b, c, d] : A)
#define iter_5(a, b, c, d, e, A) \
  for (auto&& [a, b, c, d, e] : A)
#define iter(...) \
  eval_6(__VA_ARGS__, iter_5, iter_4, iter_3, iter_2, iter_1)( \
    __VA_ARGS__ \
  )
#define pb push_back
#define eb emplace_back
#define emp emplace
#include <numeric>
using std::accumulate;
template<class T, class U>
T sum(const vc<U>& a) { return accumulate(all(a), T(0)); }
#define loop while (1)
using ll = long long;
#define FOR_1(i, n) for (int i = 0; i < n; i++)
#define FOR_2(i, a, b) for (ll i = a; i < b; i++)
#define FOR_3(i, a, b, c) for (ll i = a; i < b; i += c)
#define FOR(...) \
  eval_4(__VA_ARGS__, FOR_3, FOR_2, FOR_1, rep)(__VA_ARGS__)
#define FORR_1(i, n) for (int i = n; i-- > 0;)
#define FORR_2(i, l, r) for (ll i = r; i-- > l;)
#define FORR_3(i, l, r, d) for (ll i = r - 1; i >= l; i -= c)
#define FORR(...) \
  eval_4(__VA_ARGS__, FORR_3, FORR_2, FORR_1)(__VA_ARGS__)
#define rep(t) for (int __ = 0; __ < t; ++__)
template <class T, class F>
T binary_search(F f, T ok, T ng) {
  while (abs(ok - ng) > 1) {
    T x = (ok + ng) / 2;
    (f(x) ? ok : ng) = x;
  }
  return ok;
}
#include <algorithm>
using std::lower_bound;
using std::upper_bound;
template<class A, class T>
auto lb(A& a, const T& x) { return lower_bound(all(a), x); }
template<class A, class T>
int lbi(const A& a, const T& x) { return lb(a, x) - a.be; }
template<class A, class T>
auto ub(A& a, const T& x) { return upper_bound(all(a), x); }
template<class A, class T>
int ubi(const A& a, const T& x) { return ub(a, x) - a.be; }
#include <string>
using std::string;
using str = string;
template<class A>
int len(const A& a) { return a.size(); }
#include <iostream>
using std::cout;
#define yesno(y, n) \
  void y(bool f = 1) { cout << (f ? #y : #n) << '\n'; } \
  void n(bool f = 1) { y(!f); }
yesno(yes, no);
yesno(Yes, No);
yesno(YES, NO);
template<class T=int>
vc<T> iota(int n, T v=0) {
  vc<T> a(n);
  iota(all(a), v);
  return a;
}
#include <utility>
using std::pair;
using pii = pair<int, int>;
#include <utility>
using std::pair;
using pll = pair<ll, ll>;
using vii = vc<pii>;
using vll = vc<pll>;
#define mt make_tuple
#define ins insert
template <class T, class U>
bool chmax(T& a, const U& b) { return b > a ? a = b, 1 : 0; }
template <class T, class U>
bool chmin(T& a, const U& b) { return b < a ? a = b, 1 : 0; }
using dbl = double;
using ld = long double;
#include <tuple>
using std::tuple;
template <class... T>
using tup = tuple<T...>;
#include <queue>
using std::priority_queue;
template<class T>
using max_que = priority_queue<T>;
using std::greater;
template<class T>
using min_que = priority_queue<T, vc<T>, greater<T>>;

template<class T>
T pop(min_que<T>& q) { T v = q.top(); q.pop(); return v; }
template<class T>
T pop(max_que<T>& q) { T v = q.top(); q.pop(); return v; }
#include <algorithm>
using std::max_element;
using std::min_element;
template <class A>
auto max(const A& a) { return *max_element(all(a)); }
template <class A>
auto min(const A& a) { return *min_element(all(a)); }
template <class T>
T max(const set<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const set<T>& s) {
  return *s.be;
}
template <class T>
T max(const multiset<T>& s) {
  return *s.rbe;
}
template <class T>
T min(const multiset<T>& s) {
  return *s.be;
}
#include <bits/stdc++.h>
using namespace std;
template <typename... T>
constexpr auto min(T... a) {
  using U = common_type_t<T...>;
  return std::min(initializer_list<U>{a...});
}
template <typename... T>
constexpr auto max(T... a) {
  using U = common_type_t<T...>;
  return std::max(initializer_list<U>{a...});
}
#define fi first
#define se second
#include <functional>
using std::function;
template <class F>
using fn = function<F>;
template <class A>
A fancy(const A& a, const vc<int>& p) {
  int n = len(p);
  A b(n);
  FOR(i, n) b[i] = a[p[i]];
  return b;
}
template <class A>
vc<int> argsort(const A& a) {
  auto p = iota(len(a));
  sort(all(p), [&](int i, int j) {
    return a[i] == a[j] ? i < j : a[i] < a[j];
  });
  return p;
}
vc<int> argperm(const vc<int>& p) {
  int n = len(p);
  vc<int> a(n);
  FOR(i, n) a[p[i]] = i;
  return a;
}
template <class A>
vc<int> rankify(const A& a) {
  return argperm(argsort(a));
}
/* deprecated
*/
#include <queue>
using std::queue;
template<class T>
T pop(queue<T>& q) {
  T x = q.front();
  q.pop();
  return x;
}

#include <queue>
using std::deque;
template <class T>
T pop_front(deque<T>& q) {
  T x = q.front();
  q.pop_front();
  return x;
}
template <class T>
T pop_back(deque<T>& q) {
  T x = q.back();
  q.pop_back();
  return x;
}
template <class T>
T pop(vc<T>& a) {
  T x = a.back();
  a.pop_back();
  return x;
}
char pop(str& a) {
  char x = a.back();
  a.pop_back();
  return x;
}
class range {
  ll i, b, d;
public:
  range(ll a, ll b, ll d): i(a), b(b), d(d) {}
  range(ll a, ll b): range(a, b, a < b ? 1 : -1) {}
  range(int n): range(0, n) {}
  range& begin() { return *this; }
  range& end() { return *this; }
  range& operator++() {
    i += d;
    return *this;
  }
  bool operator!=(const range&) const {
    return d > 0 && i < b || d < 0 && i > b;
  }
  ll operator*() const { return i; }
};
template <class T>
int signum(T x) {
  return x > 0 ? 1 : x < 0 ? -1 : 0;
}
template <class T, class U>
auto divmod(T n, U k) -> pair<T, T> {
  T q = n / k;
  T r = n - q * k;
  if (signum(r) * signum(k) < 0) r += k, q--;
  return {q, r};
}
#include <random>
using std::mt19937_64;
using std::random_device;
mt19937_64 mrand(random_device{}());
int rng(int x) { return mrand() % x; }
constexpr double PI = 3.14159265358979323846;
#include <iostream>
using namespace std;
void fastio() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}
#include <iostream>
#include <iomanip>
using namespace std;
void precise_float() { cout << setprecision(18); }
template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
  return i >> p.fi >> p.se;
}
#include <tuple>
#include <iostream>
using namespace std;
template <int k = 0, class T>
void scan_tup(istream& i, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    i >> get<k>(x);
    scan_tup<k + 1>(i, x);
  }
}
template <class... T>
istream& operator>>(istream& i, tuple<T...>& x) {
  scan_tup(i, x);
  return i;
}
template <class I, class T>
I& operator>>(I& i, vc<T>& a) {
  iter(x, a) i >> x;
  return i;
}
#include <iostream>
using namespace std;
template <typename... T>
void scan(T&... a) { (cin >> ... >> a); }
#define VEC(T, a, n) VC(T, a, n); cin >> a;
#define V(T, a, n) VC(T, a, n); cin >> a;
#define VV(T, a, n, m) VVC(T, a, n, m); cin >> a;
#define VVV(T, a, n, m, l) VVC(T, a, n, m, l); cin >> a;
#define INT(...) int __VA_ARGS__; scan(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__; scan(__VA_ARGS__)
#define DBL(...) dbl __VA_ARGS__; scan(__VA_ARGS__)
#define STR(...) str __VA_ARGS__; scan(__VA_ARGS__)
#define VI(a, n) V(int, a, n)
#define VL(a, n) V(ll, a, n)
#define VII(a, n) V(pii, a, n)
#define VLL(a, n) V(pll, a, n)
#define VSTR(a, n) V(str, a, n)
template <class T, size_t n>
ostream& operator<<(ostream& os, const array<T, n>& a) {
  FOR(i, n) {
    if (i) os << ' ';
    os << a[i];
  }
  return os;
}
template <class T, size_t n>
ostream& operator<<(ostream& os, array<array<T, n>, n> a) {
  FOR(i, n) os << a[i] << '\n';
  return os;
}
#include <bits/stdc++.h>
using namespace std;
template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
  return o << p.fi << ' ' << p.se;
}
#include <bits/stdc++.h>
using namespace std;
template <int k = 0, class T>
void out_tup(ostream& o, T& x) {
  if constexpr (tuple_size<T>::value > k) {
    if constexpr (k > 0) o << ' ';
    o << get<k>(x);
    out_tup<k + 1>(o, x);
  }
}
template <class... T>
ostream& operator<<(ostream& o, tuple<T...>& x) {
  out_tup(o, x);
  return o;
}
template <class O, class T>
O& operator<<(O& o, vc<T> a) {
  FOR(i, len(a)) {
    if (i) o << ' ';
    o << a[i];
  }
  return o;
}
template <class O, class T>
O& operator<<(O& o, vvc<T> a) {
  iter(x, a) o << x << '\n';
  return o;
}
#include <iostream>
using namespace std;
template <class T, class... U>
void print(T a, U... b) {
  cout << a;
  ((cout << ' ' << b), ...);
  cout << '\n';
}
int main() {
  fastio();
  int n;
  cin >> n;
  VV(int, A, 3, n);
  const ll inf = 1ll << 60;
  VVC(ll, dp, 3, 3, -inf);
  dp[0][0] = 0;
  FOR(i, n) {
    VVC(ll, ndp, 3, 3, -inf);
    FOR(j, 3) FOR(k, 3) {
      chmax(ndp[j][k], dp[j][k] + A[k][i]);
      if (j < 2 && k < 2)
        chmax(ndp[j + 1][k + 1], dp[j][k] + A[k + 1][i]);
      if (j < 1 && k < 1)
        chmax(ndp[j + 2][k + 2], dp[j][k] + A[k + 2][i]);
      if (k >= 1) chmax(ndp[j][k - 1], dp[j][k] + A[k - 1][i]);
      if (k >= 2) chmax(ndp[j][k - 2], dp[j][k] + A[k - 2][i]);
    }
    swap(dp, ndp);
  }
  ll ans = -inf;
  FOR(j, 3) FOR(k, 3) chmax(ans, dp[j][k]);
  cout << ans << '\n';
}

yukicoder

結果

テストケース

ソースコード