結果
問題 | No.698 ペアでチームを作ろう |
ユーザー | 高森藍子 |
提出日時 | 2023-02-26 15:48:23 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 18 ms / 1,000 ms |
コード長 | 19,028 bytes |
コンパイル時間 | 2,405 ms |
コンパイル使用メモリ | 192,372 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 06:22:33 |
合計ジャッジ時間 | 3,140 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 5 ms
5,376 KB |
testcase_05 | AC | 16 ms
5,376 KB |
testcase_06 | AC | 17 ms
5,376 KB |
testcase_07 | AC | 17 ms
5,376 KB |
testcase_08 | AC | 18 ms
5,376 KB |
testcase_09 | AC | 17 ms
5,376 KB |
testcase_10 | AC | 17 ms
5,376 KB |
testcase_11 | AC | 18 ms
5,376 KB |
testcase_12 | AC | 17 ms
5,376 KB |
testcase_13 | AC | 18 ms
5,376 KB |
testcase_14 | AC | 17 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long #define ALL(a) (a).begin(),(a.end()) #define brep(n,hhh) for(int i=n-1;i>=hhh;i--) #define rep(hhh,n) for(int i=hhh;i<n;i++) #define jrep(hhh,n) for(int j=hhh;j<n;j++) #define krep(hhh,n) for(int k=hhh;k<n;k++) #define lrep(hhh,n) for(int l=hhh;l<n;l++) #define rrep(i,n) for(int i=n-1;i>=0;i--) #define out(n) cout << n <<endl; #define sot(A) sort(A.begin(),A.end()) #define rsot(A) sort(A.rbegin(),A.rend()) #define vi vector<int> #define vb vector<bool> #define vd vector<double> #define vld vector<long double> #define vc vector<char> #define vs vector<string> #define vpi vector<pair<int,int>> #define vvc vector<vector<char>> #define vvi vector<vector<int>> #define vvd vector<vector<double>> #define vvb vector<vector<bool>> #define vvvi vector<vector<vector<int>>> #define vvvpi vector<vector<vector<Pi>>> #define vvpi vector<vector<pair<int,int>>> #define vvtpi vector<vector<tuple<int,int,int>>> #define dout(x,y) cout<<x<<" "<<y<<endl; #define tout(x,y,z) cout<<x<<" "<<y<<" "<<z<<endl; #define Pi pair<int,int> #define TPi tuple<int,int,int> #define TPd tuple<double,int,int> int MOD1=1000000000+7; int MOD2=998244353; int BIG=10000000000000000; //int BBB=ppow(2,31)-1; class BIT { public: //データの長さ int n; //データの格納先 vector<int> a; //コンストラクタ BIT(int n):n(n),a(n+1,0){} //a[i]にxを加算する void add(int i,int x){ i++; if(i==0) return; for(int k=i;k<=n;k+=(k & -k)){ a[k]+=x; } } //a[i]+a[i+1]+…+a[j]を求める int sum(int i,int j){ return sum_sub(j)-sum_sub(i-1); } //a[0]+a[1]+…+a[i]を求める int sum_sub(int i){ i++; int s=0; if(i==0) return s; for(int k=i;k>0;k-=(k & -k)){ s+=a[k]; } return s; } //a[0]+a[1]+…+a[i]>=xとなる最小のiを求める(任意のkでa[k]>=0が必要) int lower_bound(int x){ if(x<=0){ //xが0以下の場合は該当するものなし→0を返す return 0; }else{ int i=0;int r=1; //最大としてありうる区間の長さを取得する //n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める while(r<n) r=r<<1; //区間の長さは調べるごとに半分になる for(int len=r;len>0;len=len>>1) { //その区間を採用する場合 if(i+len<n && a[i+len]<x){ x-=a[i+len]; i+=len; } } return i; } } }; class CR{ public: vi fac; vi finv; vi inv; int MOD; CR(int N,int M):fac(N+1),finv(N+1),inv(N+1){ MOD=M; fac[0] = fac[1] = 1; finv[0] = finv[1] = 1; inv[1] = 1; for (int i = 2; i <= N; i++){ fac[i] = fac[i - 1] * i % MOD; inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD; finv[i] = finv[i - 1] * inv[i] % MOD; } } // 二項係数計算 long long COM(int n, int k){ if (n < k) return 0; if (n < 0 || k < 0) return 0; return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD; } }; namespace internal { template <class E> struct csr { std::vector<int> start; std::vector<E> elist; csr(int n, const std::vector<std::pair<int, E>>& edges) : start(n + 1), elist(edges.size()) { for (auto e : edges) { start[e.first + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } auto counter = start; for (auto e : edges) { elist[counter[e.first]++] = e.second; } } }; // Reference: // R. Tarjan, // Depth-First Search and Linear Graph Algorithms struct scc_graph { public: scc_graph(int n) : _n(n) {} int num_vertices() { return _n; } void add_edge(int from, int to) { edges.push_back({from, {to}}); } // @return pair of (# of scc, scc id) std::pair<int, std::vector<int>> scc_ids() { auto g = csr<edge>(_n, edges); int now_ord = 0, group_num = 0; std::vector<int> visited, low(_n), ord(_n, -1), ids(_n); visited.reserve(_n); auto dfs = [&](auto self, int v) -> void { low[v] = ord[v] = now_ord++; visited.push_back(v); for (int i = g.start[v]; i < g.start[v + 1]; i++) { auto to = g.elist[i].to; if (ord[to] == -1) { self(self, to); low[v] = std::min(low[v], low[to]); } else { low[v] = std::min(low[v], ord[to]); } } if (low[v] == ord[v]) { while (true) { int u = visited.back(); visited.pop_back(); ord[u] = _n; ids[u] = group_num; if (u == v) break; } group_num++; } }; for (int i = 0; i < _n; i++) { if (ord[i] == -1) dfs(dfs, i); } for (auto& x : ids) { x = group_num - 1 - x; } return {group_num, ids}; } std::vector<std::vector<int>> scc() { auto ids = scc_ids(); int group_num = ids.first; std::vector<int> counts(group_num); for (auto x : ids.second) counts[x]++; std::vector<std::vector<int>> groups(ids.first); for (int i = 0; i < group_num; i++) { groups[i].reserve(counts[i]); } for (int i = 0; i < _n; i++) { groups[ids.second[i]].push_back(i); } return groups; } private: int _n; struct edge { int to; }; std::vector<std::pair<int, edge>> edges; }; } struct scc_graph { public: scc_graph() : internal(0) {} scc_graph(int n) : internal(n) {} void add_edge(int from, int to) { int n = internal.num_vertices(); assert(0 <= from && from < n); assert(0 <= to && to < n); internal.add_edge(from, to); } std::vector<std::vector<int>> scc() { return internal.scc(); } private: internal::scc_graph internal; }; void conf(vi &A){ for(int i:A){ cout<<i<<' '; } cout<<endl; } void conf(vvi A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<A[i][j]<<" "; } cout<<endl; } } void conf(vvpi A){ rep(0,A.size()){ jrep(0,A[i].size()){ cout<<"("<<A[i][j].first<<" "<<A[i][j].second<<")"<<" "; } cout<<endl; } } void conf(vpi A){ rep(0,A.size()){ cout <<'('<< A[i].first <<" "<<A[i].second<<')'<<" "; } cout<<endl; } int max(int a,int b){ if(a>b)return a; else return b; } int min(int a,int b){ if(a>b)return b; else return a; } int modpow(int x,int n,int mod){ int res=1; while(n>0){ int l=x%mod; if(n&1)res=(res%mod)*l%mod; x=l*l%mod; n>>=1; } return res; }//高速べき乗(modの値を返す)、計算量log(N) int ppow(int x,int n){ int res=1; while(n>0){ if(n&1)res=res*x; x=x*x; n>>=1; } return res; }//高速べき乗、計算量log(N) int modinv(int a, int m) { int b = m, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; }//拡張EuClidの互除法、逆元を返す,a,mが互いに素ならOK、mがMOD,log(a); vi smallest_prime_factors(int n) { vi spf(n + 1); for (int i = 0; i <= n; i++) spf[i] = i; for (int i = 2; i * i <= n; i++) { if (spf[i] == i) { for (int j = i * i; j <= n; j += i) { if (spf[j] == j) { spf[j] = i; } } } } return spf; } vector<int> enumdiv(int n) { vector<int> S; for (int i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); } sort(S.begin(), S.end()); return S; }//与えられた1つの数の約数をvectorで昇順で返す(重複なし),計算量√N vi soinsu(int N){ vi T; int n=N; int k=2; while(k*k<=n){ if(N%k==0){ N=N/k; T.push_back(k); } else{ k++; } } if(N!=1)T.push_back(N); if(T.size()==0){ T.push_back(n); } return T; }//素因数分解した結果をviで返す(sort済み),O(√N) int legendre(int N,int k){ int ans=0; int K=k; while(N>=K){ ans+=N/K; K*=k; } return ans; }//N!がkで何回割ることが出来るか vb Eratosthenes(int N){ vb IsPrime(N+1,true); IsPrime[0] = false; // 0は素数ではない IsPrime[1] = false; // 1は素数ではない for(int i=2; i*i<=N; ++i) // 0からsqrt(max)まで調べる if(IsPrime[i]) // iが素数ならば for(int j=2; i*j<=N; ++j) // (max以下の)iの倍数は IsPrime[i*j] = false; return IsPrime; }//Nまでの数が素数か素数でないかを返す、計算量nloglogn /*int clk=1; void clkdfs(vvi &A,vpi &B,int v){ if(seen[v])return ; seen[v] = true; // v を訪問済にする B[v].first=clk; clk++; // v から行ける各頂点 next_v について for (int next_v:A[v]) { if (seen[next_v-1]) continue; // next_v が探索済だったらスルー clkdfs(A,B,next_v-1); // 再帰的に探索 } B[v].second=clk; clk++; }*/ /*int W,H; void dfs(vvi &A,int h,int w){ //if(A[h][w]==0)return; A[h][w] =0; // v を訪問済にする vi dh={-1,-1,-1,0,0,1,1,1}; vi dw={-1,0,1,-1,1,-1,0,1}; rep(0,8){ if(h+dh[i]>=0&&h+dh[i]<=H-1&&w+dw[i]>=0&&w+dw[i]<=W-1&&A[h+dh[i]][w+dw[i]]==1){ //dout(h+dh[i],w+dw[i]); dfs(A,h+dh[i],w+dw[i]); // 再帰的に探索 } } }*/ int lgcd(int A, int B){ int a,b,C; while (A!=0 && B!=0){ if (A>B){ a=A/B; A=A-B*a; }else{ b=B/A; B=B-A*b; } } C=max(A,B); return C; } void YN(bool A){ if(A){ out("Yes"); }else{ out("No"); } } double max(double a,double b){ if(a>b){ return a; }else{ return b; } } double min(double a,double b){ if(a>b){ return b; }else{ return a; } } /*int H,W; void dfs(vs &G,int h,int w,vvi &seen){ vi dh={1,0,-1,0}; vi dw={0,1,0,-1}; rep(0,4){ if(h+dh[i]>=0&&h+dh[i]<=H-1&&w+dw[i]>=0&&w+dw[i]<=W-1&&G[h+dh[i]][w+dw[i]]=='.'&&seen[h+dh[i]][w+dw[i]]==1000000000){ seen[h+dh[i]][w+dw[i]]=seen[h][w]+1; dfs(G,h+dh[i],w+dw[i],seen); // 再帰的に探索 } } //A[h][w]=1; }*/ vvi mat_mul(vvi &a, vvi &b,int MOD) { vvi res(a.size(), vi(b[0].size())); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b[0].size(); j++) { for (int k = 0; k < b.size(); k++) { (res[i][j] += a[i][k] * b[k][j]) %= MOD; } } } return res; } vvi mat_pow(vvi a, int n,int MOD) { vvi res(a.size(), vi(a.size())); // 単位行列で初期化 for (int i = 0; i < a.size(); i++) res[i][i] = 1; // 繰り返し二乗法 while (n > 0) { if (n & 1) res = mat_mul(a, res,MOD); a = mat_mul(a, a,MOD); n >>= 1; } return res; } int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} segtree(int n) : segtree(std::vector<S>(n, e())) {} segtree(const std::vector<S>& v) : _n((v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template <bool (*f)(S)> int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; struct dsu { public: dsu() : _n(0) {} dsu(int n) : _n(n), parent_or_size(n, -1) {} int merge(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y); parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; return parent_or_size[a] = leader(parent_or_size[a]); } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } std::vector<std::vector<int>> groups() { std::vector<int> leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector<std::vector<int>> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector<int>& v) { return v.empty(); }), result.end()); return result; } private: int _n; // root node: -1 * component size // otherwise: parent std::vector<int> parent_or_size; }; vi dikstra(int s,int V,vector<vector<pair<int,int>>> &G){ vi d(V,BIG); priority_queue<Pi,vector<Pi>,greater<Pi>> que; d[s]=0; que.push(Pi(0,s));//Pi(距離、向かう頂点) while(!que.empty()){ Pi p=que.top();que.pop(); int v=p.second; if(d[v]<p.first)continue; rep(0,G[v].size()){ int a=G[v][i].second; int b=G[v][i].first; if(d[a]>d[v]+b){ d[a]=d[v]+b; que.push(Pi(d[a],a)); } } } return d; }//始点は0start Pi op(Pi a, Pi b) { return max(a, b); } Pi e() { return Pi(-2,-1); } //int target; //bool f(int v) { return v >= target; } /*int flg=-1; bool gg=false; void loopdfs(int a,int v,vvi &G,vb &seen,vi &loop){ if(seen[a])return ; seen[a]=true; //out(a); for (auto nv : G[a]) { if(nv==v)continue; if(gg)continue; if (seen[nv]){ flg=nv; gg=true; break; } loopdfs(nv,a,G,seen,loop); } if(gg){ loop.push_back(a); } if(flg==a)gg=false; }*/ //bool flag=false; void kdfs(vvi &G,vi &seen,int v,int d){ if(seen[v]!=-1)return ; seen[v] = d; // v を訪問済にするて for (int nv:G[v]) { if (seen[nv]!=-1) continue; // next_v が探索済だったらスルー kdfs(G,seen,nv,(d+1)%2); // 再帰的に探索 } } /*void dfs(vs &S,int h,int w,int px,int py,vvi &dp,int &ans){ if(dp[h][w]==-1)return; if(px==-1)dp[h][w]=0; if(px!=-1){ dp[h][w] =0; } // v を訪問済にする vi dh={1,0}; vi dw={0,1}; rep(0,8){ if(h+dh[i]>=0&&h+dh[i]<=H-1&&w+dw[i]>=0&&w+dw[i]<=W-1&&A[h+dh[i]][w+dw[i]]==1){ //dout(h+dh[i],w+dw[i]); dfs(A,h+dh[i],w+dw[i]); // 再帰的に探索 } } }*/ int rec(vi &A,int N,int bit,vi &dp){ if (dp[bit]!=-1){ //out(bit); return dp[bit]; } vi F; rep(0,N){ if((1<<i)&bit)F.push_back(i); } //conf(F) if(F.size()==2){ int k=A[F[0]]; k^=A[F[1]]; return dp[bit]=k; } int res = 0; //int prev_bit = bit & ~(1<<v); rep(0,N){ jrep(0,N){ if (!((bit & (1<<i))&&(bit&(1<<j)))) continue; int prev_bit=bit&(~(1<<i))&(~(1<<j)); //out(prev_bit); if (res < (rec(A,N,prev_bit, dp)+(A[i]^A[j])) ) { res = rec(A,N,prev_bit, dp)+(A[i]^A[j]); } } } return dp[bit] = res; // メモしながらリターン } signed main(){ int N;cin>>N; vi A(N); rep(0,N){ cin>>A[i]; } vi dp((1<<N),-1); out(rec(A,N,(1<<N)-1,dp)); //conf(dp); }