結果
問題 | No.2889 Rusk |
ユーザー | にしろ |
提出日時 | 2024-09-16 22:11:27 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 7,584 bytes |
コンパイル時間 | 5,820 ms |
コンパイル使用メモリ | 334,468 KB |
実行使用メモリ | 53,376 KB |
最終ジャッジ日時 | 2024-09-16 22:11:43 |
合計ジャッジ時間 | 13,794 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 7 ms
5,376 KB |
testcase_15 | AC | 26 ms
11,264 KB |
testcase_16 | AC | 66 ms
24,064 KB |
testcase_17 | AC | 19 ms
8,832 KB |
testcase_18 | AC | 55 ms
20,736 KB |
testcase_19 | AC | 102 ms
37,220 KB |
testcase_20 | AC | 140 ms
45,020 KB |
testcase_21 | AC | 108 ms
37,344 KB |
testcase_22 | AC | 91 ms
32,332 KB |
testcase_23 | AC | 67 ms
25,984 KB |
testcase_24 | AC | 124 ms
44,544 KB |
testcase_25 | AC | 68 ms
25,856 KB |
testcase_26 | AC | 102 ms
36,352 KB |
testcase_27 | AC | 132 ms
46,208 KB |
testcase_28 | AC | 77 ms
28,416 KB |
testcase_29 | AC | 82 ms
29,440 KB |
testcase_30 | AC | 80 ms
29,312 KB |
testcase_31 | AC | 151 ms
45,696 KB |
testcase_32 | AC | 58 ms
21,376 KB |
testcase_33 | AC | 16 ms
8,064 KB |
testcase_34 | AC | 153 ms
53,376 KB |
testcase_35 | AC | 152 ms
53,320 KB |
testcase_36 | AC | 151 ms
53,244 KB |
testcase_37 | AC | 151 ms
53,228 KB |
testcase_38 | AC | 150 ms
53,248 KB |
testcase_39 | AC | 110 ms
48,624 KB |
testcase_40 | AC | 92 ms
38,600 KB |
testcase_41 | AC | 124 ms
50,872 KB |
testcase_42 | AC | 79 ms
35,980 KB |
testcase_43 | AC | 39 ms
18,432 KB |
testcase_44 | AC | 102 ms
45,748 KB |
testcase_45 | AC | 79 ms
35,696 KB |
testcase_46 | AC | 23 ms
12,032 KB |
testcase_47 | AC | 42 ms
19,840 KB |
testcase_48 | AC | 90 ms
41,472 KB |
testcase_49 | AC | 2 ms
5,376 KB |
testcase_50 | AC | 2 ms
5,376 KB |
testcase_51 | AC | 2 ms
5,376 KB |
testcase_52 | AC | 2 ms
5,376 KB |
testcase_53 | AC | 2 ms
5,376 KB |
testcase_54 | AC | 154 ms
53,376 KB |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using ul = unsigned long; using ld = long double; using st = string; using mint = atcoder::modint998244353; using Mint = atcoder::modint1000000007; #define vl vector<ll> #define vvl vector<vector<ll>> #define vvvl vector<vector<vector<ll>>> #define vvvvl vector<vector<vector<vector<ll>>>> #define vd vector<ld> #define vvd vector<vector<ld>> #define vvvd vector<vector<vector<ld>>> #define vb vector<bool> #define vvb vector<vector<bool>> #define vvvb vector<vector<vector<bool>>> #define vs vector<string> #define vvs vector<vector<string>> #define vvvs vector<vector<vector<string>>> #define vp vector<pair<ll,ll>> #define vvp vector<vector<pair<ll,ll>>> #define vvvp vector<vector<vector<pair<ll,ll>>>> #define vm vector<mint> #define vvm vector<vector<mint>> #define vM vector<Mint> #define vvM vector<vector<Mint>> #define cmx(n,v) n=n<v?v:n #define cmn(n,v) n=n>v?v:n #define all(n) begin(n),end(n) #define nxp(a) next_permutation(all(a)) #define rev(n) reverse(all(n)) #define sor(n) stable_sort(all(n)) #define rep(i,n) for(ll i=0;i<(n);++i) #define reprev(i,n) for(ll i=n-1;0<=i;--i) #define rrep(i,a,n) for(ll i=a;i<(n);++i) #define sz(n) n.size() #define bit(j,i) (i&(1<<j)) #define yn(x) cout << (x?"Yes":"No") << endl; #define lb(vec,src) lower_bound(vec.begin(),vec.end(),src)-vec.begin() #define ub(vec,src) upper_bound(vec.begin(),vec.end(),src)-vec.begin() #define lb2(vec,src) *lower_bound(vec.begin(),vec.end(),src) #define ub2(vec,src) *upper_bound(vec.begin(),vec.end(),src) #define mne1(a) min_element(all(a)) #define mxe1(a) max_element(all(a)) #define mne2(a) *min_element(all(a)) #define mxe2(a) *max_element(all(a)) #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} const ll inf = 9e18; ll calc_digit(ll N){ ll res = 0; while(N>0){ res++; N/=10; } return res; } ll factorial(ll n, ll mod = 1e18) { ll ans = 1; for(ll i = n; i >= 2; i--) ans = (ans * i) % mod; return ans; } ll round_up(ll x,ll y){ return (x+y-1)/y; } ll floor_int(ll x,ll m){ ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換える return (x-r)/m; //return } ll rmd(ll x,ll m){ ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換える return r; } ll rmd_2(ll x,ll m){ ll r=(x%m+m)%m; //負の剰余を正の剰余に置き換える return (m-r)%m; //return } ll bubble_sort(vl& a,ll& n){ ll res=0; rep(i,n-1){ for(ll j=n-1;j>i;j--){ if(a[j-1]>a[j]){ swap(a[j-1],a[j]); res++; } } } return res; } ll sum_v(vl a){ ll res=0; ll n=sz(a); rep(i,n) res+=a[i]; return res; } ll stair_sum(ll from,ll to){ return (from+to)*(to-from+1)/2; } ll Power(ll var, ll p) { if (p == 1) return var; ll ans = Power(var * var, p / 2); if (p & 1) ans *= var;; return ans; } ll cnt_01(ll n,ll now){ ll res=0; res+=(n/now)*(now/2); if(n%now>=now/2) res+=n%now-(now/2)+1; return res; } mint m_Power(mint var,ll p) { if (p == 1) return var; mint ans = m_Power(var * var, p / 2); if (p & 1) ans *= var;; return ans; } Mint M_Power(Mint var,ll p) { if (p == 1) return var; Mint ans = M_Power(var * var, p / 2); if (p & 1) ans *= var;; return ans; } bool is_prime(ll N){ if(N==1) return false; if(N==2) return true; if(N%2==0) return false; for(ll p=3;p*p<=N;p+=2) if(N%p==0) return false; return true; } bool in_out(ll x,ll y,ll h,ll w){ return 0<=x and x<h and 0<=y and y<w; } bool dis_solve1(ll x1,ll x2,ll y1,ll y2,ll r){ ll xx=(x1-x2),yy=(y1-y2); ll dis=xx*xx+yy*yy; return (r*r==dis); } bool dis_solve2(ll x1,ll x2,ll y1,ll y2,ll d1,ll d2){ ll xx=(x1-x2),yy=(y1-y2),r1=(d1+d2),r2=(d1-d2); ll dis=xx*xx+yy*yy; return (r2*r2<=dis&&dis<=r1*r1); } void printl(vl v,ll len=0){ ll vsz=min(len,ll(v.size())); for(ll i=0;i<vsz;i++){ cout << v[i] << endl; } } void prints(vs v){ ll vsz=v.size(); for(ll i=0;i<vsz;i++){ cout << v[i] << endl; } } vl p_list(ll n){ vl res; vb check(n+1); for(ll i=2;i<=n;i++){ if(check[i]) continue; res.push_back(i); ll ii=i; while(ii<=n){ check[ii]=true; ii+=i; } } return res; } vl cumulative_sum(vl a){ ll s=sz(a); vl b(s+1,0); for(ll i=0;i<s;i++){ b[i+1]=a[i]+b[i]; } return b; } vl n_num(ll a,ll n){ vl res; while(a){ res.push_back(a%n); a/=n; } rev(res); return res; } vl c_press(vl a){ ll n=sz(a); vl res=a,c=a; sor(c); uniq(c); rep(i,n) res[i]=lb(c,res[i]); return res; } vl min_fact(ll n){ vl pl; vl res(n+1,-1); for(ll d=2;d<=n;d++){ if(res[d]==-1){ res[d]=d; pl.push_back(d); } for(ll p:pl){ if(p*d>n||p>res[d]) break; res[p*d]=p; } } return res; } vvl to_grid(vl &a,ll k){ ll n=sz(a); ll m=(n+k-1)/k; vvl b(k,vl(m,inf)); rep(i,n) b[i%k][i/k]=a[i]; return b; } vvl rotate_ll(vvl& V2d,ll wise){ vvl a=V2d; ll h=sz(a),w=sz(a[0]); vvl res(w,vl(h)); if(wise) {rep(i,h)rep(j,w) res[j][h-i-1]=a[i][j];} else {rep(i,h)rep(j,w) res[w-j-1][i]=a[i][j];} return res; } vs rotate_st(vs s,ll wise){ vs a=s; ll h=sz(a),w=sz(a[0]); vs res(w); rep(i,w) res[i].append(h,'.'); if(wise) {rep(i,h)rep(j,w) res[j][h-i-1]=a[i][j];} else {rep(i,h)rep(j,w) res[w-j-1][i]=a[i][j];} return res; } vp prime_factorize(ll N){ vp res; for (ll a = 2; a * a <= N; ++a) { if (N % a != 0) continue; ll ex = 0; while (N % a == 0) { ex++; N /= a; } res.push_back({a, ex}); } if (N != 1) res.push_back({N, 1}); return res; } template <typename T> void input(T &a) { cin >> a; }; template <typename T1, typename... T2> void input(T1&a, T2 &...b) { cin >> a; input(b...); }; template<typename T = ll> vector<T> rd(size_t n) { vector<T> ts(n); for (size_t i = 0; i < n; i++) cin >> ts[i]; return ts; } template<typename TV, const ll N> void read_tuple_impl(TV&) {} template<typename TV, const ll N, typename Head, typename... Tail> void read_tuple_impl(TV& ts) { get<N>(ts).emplace_back(*(istream_iterator<Head>(cin))); read_tuple_impl<TV, N + 1, Tail...>(ts); } template<typename... Ts> decltype(auto) read_tuple(size_t n) { tuple<vector<Ts>...> ts; for (size_t i = 0; i < n; i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts); return ts; } ll di[8]={1,-1,0,0,1,1,-1,-1}; ll dj[8]={0,0,1,-1,1,-1,-1,1}; //std::setprecision(15); //2^29<10^9 int main(){ ios::sync_with_stdio(0); cin.tie(0); ll n; cin >> n; vector taste(n,vector<ll>(3)); for(ll j=0;j<3;j++)for(ll i=0;i<n;i++){ cin >> taste[i][j]; } vector dp(n+1,vector(3,vector<ll>(3,-inf))); dp[0][0][0]=0; for(ll i=0;i<n;i++){ for(ll x=0;x<3;x++)for(ll y=0;y<3;y++){ if(dp[i][x][y]==-inf) continue; for(ll a=0;a<2;a++)for(ll b=0;b<2;b++){ ll nx=a+x,ny=b+y; if(nx>2||ny>2) continue; dp[i+1][nx][ny]=max(dp[i+1][nx][ny],dp[i][x][y]+taste[i][nx%2+ny%2]); } } } ll ans=-inf; for(ll x=0;x<3;x++)for(ll y=0;y<3;y++){ ans=max(ans,dp[n][x][y]); } cout << ans; }