結果
問題 | No.1345 Beautiful BINGO |
ユーザー |
![]() |
提出日時 | 2021-01-16 13:35:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 744 ms / 2,000 ms |
コード長 | 1,816 bytes |
コンパイル時間 | 2,080 ms |
コンパイル使用メモリ | 181,148 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-28 11:48:25 |
合計ジャッジ時間 | 15,979 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long typedef pair<int,int> P; int INF = 3e18+7; int mod = 1e9+7; int dx[] = {1, 0,-1, 0, 1, 1,-1,-1}; int dy[] = {0, 1, 0,-1, 1,-1, 1,-1}; signed main() { int N,M; 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]; } } int ans = INF; for(int i = 0; i < (1 << (N+2)); i++) { int res = 0; int sum = 0; vector<vector<bool>>flag(N,vector<bool>(N)); for(int j = 0; j < N; j++) { if(!(1 & (i >> j))) { continue; } for(int k = 0; k < N; k++) { sum += A[j][k]; flag[j][k] = true; } res++; } if(1 & (i >> N)) { res++; for(int j = 0; j < N; j++) { if(!flag[j][j]) { flag[j][j] = true; sum += A[j][j]; } } } if(1 & (i >> (N+1))) { res++; for(int j = 0; j < N; j++) { if(!flag[j][N-j-1]) { flag[j][N-j-1] = true; sum += A[j][N-j-1]; } } } if(res+N < M) { continue; } vector<int>x; for(int j = 0; j < N; j++) { int sum2 = 0; for(int k = 0; k < N; k++) { if(!flag[k][j]) { sum2 += A[k][j]; } } x.push_back(sum2); } sort(x.begin(),x.end()); for(int j = 0; j < M-res; j++) { sum += x[j]; } ans = min(ans,sum); } cout << ans << endl; }