結果

問題 No.698 ペアでチームを作ろう
ユーザー jupiro
提出日時 2020-01-15 14:53:40
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 20 ms
コード長 1,600 Byte
コンパイル時間 980 ms
使用メモリ 5,524 KB
最終ジャッジ日時 2020-01-15 14:53:43

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 4 ms
3,312 KB
sample2.txt AC 4 ms
3,304 KB
sample3.txt AC 0 ms
3,660 KB
test1.txt AC 4 ms
3,400 KB
test2.txt AC 8 ms
3,556 KB
test3.txt AC 20 ms
5,376 KB
test4.txt AC 16 ms
5,432 KB
test5.txt AC 20 ms
5,400 KB
test6.txt AC 20 ms
5,384 KB
test7.txt AC 20 ms
5,348 KB
test8.txt AC 16 ms
5,448 KB
test9.txt AC 16 ms
5,524 KB
test10.txt AC 16 ms
5,524 KB
test11.txt AC 16 ms
5,472 KB
test12.txt AC 20 ms
5,388 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long mod = 1000000007LL;
//const long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;

vector<vector<ll>> dp;
ll N;
vector<ll> a;

ll dfs(ll S, ll pre) {
	if (pre != -1 && dp[S][pre] != -1) {
		return dp[S][pre];
	}
	if (S == (1LL << N) - 1) return 0;
	ll res = 0;
	ll cnt = 0;
	for (ll i = 0; i < N; i++) {
		if ((S >> i) & 1) cnt++;
	}

	for (ll i = 0; i < N; i++) {
		if (!((S >> i) & 1)) {
			if (cnt & 1) {
				chmax(res, dfs((S + (1LL << i)), i) + (a[i] ^ a[pre]));
			}

			else chmax(res, dfs((S + (1LL << i)), i));
		}
	}

	if (pre == -1) return res;
	else return dp[S][pre] = res;

}
int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/
	scanf("%lld", &N);
	a.resize(N); for (ll i = 0; i < N; i++) scanf("%lld", &a[i]);
	dp = vector<vector<ll>>(1 << N, vector<ll>(N, -1));
	
	cout << dfs(0, -1) << endl;
	return 0;
}
0