結果
問題 | No.1345 Beautiful BINGO |
ユーザー |
|
提出日時 | 2021-01-16 13:23:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 686 ms / 2,000 ms |
コード長 | 1,956 bytes |
コンパイル時間 | 2,160 ms |
コンパイル使用メモリ | 206,508 KB |
最終ジャッジ日時 | 2025-01-17 21:54:52 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < n; i++)#define rep2(i, x, n) for(int i = x; i <= n; i++)#define rep3(i, x, n) for(int i = x; i >= n; i--)#define each(e, v) for(auto &e: v)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define rall(x) x.rbegin(), x.rend()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;const int MOD = 1000000007;//const int MOD = 998244353;const int inf = (1<<30)-1;const ll INF = (1LL<<60)-1;template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};struct io_setup{io_setup(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout << fixed << setprecision(15);}} io_setup;int main(){int N, M;cin >> N >> M;vector<vector<int>> c(N, vector<int>(N));rep(i, N){rep(j, N) cin >> c[i][j];}int ans = inf;rep(i, 2) rep(j, 2) rep(k, 1<<N){vector<vector<bool>> used(N, vector<bool>(N, false));rep(l, N){if(i) used[l][l] = true;if(j) used[N-1-l][l] = true;}rep(x, N){if(k&(1<<x)){rep(y, N) used[x][y] = true;}}int tmp = 0;rep(x, N){rep(y, N){if(used[x][y]) tmp += c[x][y];}}vector<int> ws(N);rep(y, N){int s = 0;rep(x, N){if(!used[x][y]) s += c[x][y];}ws[y] = s;}sort(all(ws));int rem = M-i-j-__builtin_popcount(k);if(rem > N) continue;rep(l, rem) tmp += ws[l];chmin(ans, tmp);}cout << ans << '\n';}