結果
問題 | No.1360 [Zelkova 4th Tune] 協和音 |
ユーザー |
|
提出日時 | 2021-01-22 21:34:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 1,092 bytes |
コンパイル時間 | 2,354 ms |
コンパイル使用メモリ | 167,080 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-27 21:59:00 |
合計ジャッジ時間 | 8,330 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
// #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define all(x) x.begin(), x.end() #define lch (o << 1) #define rch (o << 1 | 1) typedef double db; typedef long long ll; typedef unsigned int ui; typedef pair<int, int> pint; typedef tuple<int, int, int> tint; const int N = 18 + 2; const int INF = 0x3f3f3f3f; const ll INF_LL = 0x3f3f3f3f3f3f3f3f; int a[N]; int b[N][N]; int getBit(int x, int pos) { return (x >> pos) & 1; } int main() { ios::sync_with_stdio(0); int n; cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> b[i][j]; int sta = 1 << n; ll sum = a[0]; int ans = 1; for (int s = 0; s < sta; s++) { ll tmp = 0; for (int i = 0; i < n; i++) { if (getBit(s, i)) tmp += a[i]; for (int j = i + 1; j < n; j++) if (getBit(s, i) && getBit(s, j)) tmp += b[i][j]; } if (tmp > sum) { sum = tmp; ans = s; } } cout << sum << endl; for (int i = 0; i < n; i++) if (getBit(ans, i)) cout << i + 1 << ' '; cout << endl; return 0; }