結果
問題 | No.1360 [Zelkova 4th Tune] 協和音 |
ユーザー |
|
提出日時 | 2021-01-22 21:59:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 346 ms / 2,000 ms |
コード長 | 1,083 bytes |
コンパイル時間 | 2,404 ms |
コンパイル使用メモリ | 198,396 KB |
最終ジャッジ日時 | 2025-01-18 04:18:15 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 47 |
ソースコード
#define _USE_MATH_DEFINES#include <bits/stdc++.h>using namespace std;signed main() {ios::sync_with_stdio(false); cin.tie(0);int n;cin >> n;long long ans = -(1LL << 60);vector<int> a(n);for (auto& x : a) cin >> x;vector<vector<int>> b(n, vector<int>(n));for (auto& v : b) for (auto& x : v) cin >> x;vector<int> ans_sounds;for (int mask = 0; mask < (1 << n); mask++) {long long cur = 0;for (int i = 0; i < n; i++) if ((mask >> i) & 1) cur += a[i];long long bonus = 0;for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {if (((mask >> i) & 1) && ((mask >> j) & 1)) bonus += b[i][j];}assert(bonus % 2 == 0);bonus >>= 1;cur += bonus;if (cur > ans && mask > 0) {ans = cur;ans_sounds.clear();for (int i = 0; i < n; i++) if ((mask >> i) & 1) ans_sounds.emplace_back(i + 1);}}assert(!ans_sounds.empty());cout << ans << endl;for (int i = 0; i < (int) ans_sounds.size(); i++) {if (i > 0) cout << " ";cout << ans_sounds[i];}cout << endl;return 0;}