#788382 (C++17) No.698 ペアでチームを作ろう

提出ソース

結果

問題	No.698 ペアでチームを作ろう
ユーザー	pythontanuki
提出日時	2022-08-13 13:00:24
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	7 ms / 1,000 ms
コード長	6,808 bytes
コンパイル時間	2,669 ms
コンパイル使用メモリ	221,536 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-24 16:50:43
合計ジャッジ時間	3,536 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	3 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	3 ms 6,944 KB
testcase_05	AC	6 ms 6,940 KB
testcase_06	AC	6 ms 6,940 KB
testcase_07	AC	6 ms 6,940 KB
testcase_08	AC	6 ms 6,944 KB
testcase_09	AC	7 ms 6,940 KB
testcase_10	AC	6 ms 6,940 KB
testcase_11	AC	6 ms 6,944 KB
testcase_12	AC	7 ms 6,944 KB
testcase_13	AC	6 ms 6,940 KB
testcase_14	AC	6 ms 6,944 KB

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

ソースコード

raw source code

/*
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_set>
*/
#include <bits/stdc++.h>
/*
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
*/
using namespace std;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const int MX = 200005;
const int dx[4] = {-1,0,1,0};
const int dy[4] = {0,-1,0,1};
const int di[8] = {1,1,1,0,0,-1,-1,-1};
const int dj[8] = {1,0,-1,1,-1,1,0,-1};
int getint(){int x; scanf("%d",&x);return x;}
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return;}
# define ll long long
# define fi first
# define se second
# define be begin
# define en end
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vm vector<mint>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define vps vector<pair<string, string>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define S sort
# define N next_permutation
# define rep(i,n) for(int i = 0; i < (n); ++i)
# define rrep(i, a, b) for(int i = a; i < b; i++)
# define lrep(i, a, b) for(ll i = a; i < b; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define slrep(i, a, b) for(ll i = a; i <= b; ++i)
# define drep(i, a, b) for(int i = a; i >= b; --i)
# define dlrep(i, a, b) for(ll i = a; i >= b; --i)
# define ALL(obj) (obj).begin(), (obj).end()
# define rALL(obj) (obj).rbegin(), (obj).rend()
# define Pll pair<ll, ll>
# define P pair<int,int>
void read() {}
template <typename T, class... U> void read(T &t, U &...u) { cin >> t; read(u...); }
void out() { cout << endl; }
template <typename T, class... U, char sep = ' '> void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); }
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }

/*
struct combination {
   vector<mint> fact, ifact;
   combination(int n):fact(n+1),ifact(n+1) {
   assert(n < mod);
   fact[0] = 1;
   for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
   ifact[n] = fact[n].inv();
   for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
}

mint operator()(int n, int k) {
   if (k < 0 || k > n) return 0;
   return fact[n]*ifact[k]*ifact[n-k];
  }
};
*/

ll gcd (ll x, ll y) {return x ? gcd(y%x, x) : y;}

ll lcm (ll x, ll y) {return x/gcd(x,y)*y;}


vector<pair<ll,int>> factorize(ll n) {
    vector<pair<ll,int>> res;
    for(ll i = 2; i*i <= n; ++i) {
        if(n%i) continue;
        res.eb(i,0);
        while(n%i == 0) {
            n /= i;
            res.back().se++;
        }
    }
    if(n != 1) res.eb(n,1);
    return res;
}

ll binary_pow(ll a, ll n) {
    if(n == 0) return 1;
    ll x = binary_pow(a,n/2);
    x *= x;
    if(n%2) x *= a;
    return x;
}


ll pascal[4500][4500];

void pascal_init() {
    pascal[0][0] = 1;
    rep(i,4400) {
        rep(j,i+1) {
            pascal[i+1][j] += pascal[i][j];
            pascal[i+1][j+1] += pascal[i][j];
        }
    }
}


vector<bool> prime_table(ll n) {
    vector<bool> prime(n+1,true);
    prime[0] = false;
    prime[1] = false;
    for(ll i = 2; i*i <= n; i++) {
        if(!prime[i]) continue;
        for(int j = i*i; j <= n; j += i) prime[j] = false;
    }
    return prime;
}


vector<ll> divisor(ll n) {
    vl res;
    for(ll i = 1; i*i <= n; ++i) {
        if(n%i == 0) {
            res.pb(i);
            if(i*i != n) res.pb(n/i);
        }
    }
    S(ALL(res));
    return res;
}


C input_complex() {
    double x, y;
    read(x,y);
    return C(x,y);
}


vector<pair<char, int>> runLengthEncoding(string s) {
    int n = s.length();
    vector<pair<char, int>> res;
    char pre = s[0];
    int cnt = 1;
    rrep(i, 1, n) {
        if (pre != s[i]) {
            res.push_back({ pre, cnt });
            pre = s[i];
            cnt = 1;
        }
        else cnt++;
    }

    res.push_back({ pre, cnt });
    return res;
}


vector<int> topologicalSort(vector<vector<int>> &G, vector<int> &inDegree, int nodenum) {
    vector<int> res; //答え用の配列
    priority_queue<int,vector<int>, greater<>> q; //入次数が0の頂点の処理待ち //辞書順が最小のものを返す

    rep(i,nodenum) if(inDegree[i] == 0) q.push(i);

    while(sz(q)) {
        int v = q.top(); q.pop();
        rep(i,sz(G[v])) {
            int u = G[v][i];
            --inDegree[u];
            if(inDegree[u] == 0) q.push(u);
        }
        res.push_back(v);
}
    return res;
}


template<class T>
vector<long long> dijkstra(vector<vector<pair<int, T>>>& graph, int start)
{
    int n = graph.size();
    vector<long long> res(n, 2e18);
    res[start] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> que;
    que.push({0, start});
    while(!que.empty())
    {
        auto[c, v] = que.top();
        que.pop();
        if(res[v] < c) continue;
        for(auto[cost, nxt]: graph[v])
        {
            if(res[v]+cost < res[nxt]) {
                res[nxt] = res[v] + cost;
                que.push(Pll(res[nxt], nxt));
            }
        }
    }
    return res;
}

/*
vvi to;
vi go_in;
vi go_out;
vb seen;

void dfs_time_stamp(int v, int &ptr) {
    go_in[v] = ptr++; //行きがけ
    seen[v] = true;
    for (auto u : to[v]) {
        if (seen[u]) continue;
        dfs(u,ptr);
    }
    go_out[v] = ptr++;//帰りがけ
}
*/

/*
vvi to;

void dfs(int v, int p = -1) {
    for (auto u : to[v]) {
        if(u == p) continue;
        dfs(u,v);
    }
}
*/


struct Solver {
  void solve() {
    int n;
    read(n);
    vl A(n);
    rep(i,n) read(A[i]);
    //dp[msk] : 集合mskの人がpairになっているときの戦闘力の最大値
    vector<ll> dp(1<<14);
    rep(msk,1<<n) {
    	rep(a,n) rrep(b,a+1,n) {
    		if(!(msk & (1 << a)) and (!(msk & (1 << b)))) {
    			chmax(dp[msk + (1<<a) + (1<<b)], dp[msk]+(A[a] ^ A[b]));
    		}
    	}
    }
    cout << dp[(1<<n)-1] << endl;
  }
};


int main() {
  int ts = 1;
  // scanf("%d",&ts);
  rep(ti,ts) {
    Solver solver;
    solver.solve();
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード