結果
問題 | No.1345 Beautiful BINGO |
ユーザー |
|
提出日時 | 2023-01-08 03:32:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 339 ms / 2,000 ms |
コード長 | 1,173 bytes |
コンパイル時間 | 1,539 ms |
コンパイル使用メモリ | 175,076 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-15 05:10:46 |
合計ジャッジ時間 | 7,913 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m, ans = 1 << 30; cin >> n >> m; vector<vector<int>> A(n, vector<int>(n)); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ cin >> A[i][j]; } } for(int i = 0; i < (1 << (n + 2)); i++){ int need = m - __builtin_popcount(i); if(need > n) continue; int s = 0; vector<int> b(n); bool nnm1 = i >> n & 1, nnm2 = (i >> (n + 1)) & 1; for(int y = 0; y < n; y++){ for(int x = 0; x < n; x++){ if(i >> x & 1){ s += A[y][x]; continue; } if(nnm1 && y == x){ s += A[y][x]; continue; } if(nnm2 && y + x == n - 1){ s += A[y][x]; continue; } b[y] += A[y][x]; } } sort(b.begin(), b.end()); for(int y = 0; y < need; y++)s += b[y]; ans = min(ans, s); } cout << ans << '\n'; }