結果

問題 No.1345 Beautiful BINGO
ユーザー 👑 SPD_9X2
提出日時 2021-01-16 14:04:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 395 ms / 2,000 ms
コード長 1,779 bytes
コンパイル時間 2,001 ms
コンパイル使用メモリ 202,420 KB
最終ジャッジ日時 2025-01-17 22:30:21
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 61
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:21:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   21 |     scanf("%lld%lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:28:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   28 |             scanf("%lld",&A[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <limits>
#include <numeric>
#include <type_traits>
#include <bitset>
#include <queue>

using namespace std;

#define rep(i,n,m) for(int (i)=(n);(i)<(m);(i)++)
#define rrep(i,n,m) for(ll (i)=(n);(i)>(m);(i)--)
using ll = long long;
const ll mod = 998244353;
const ll inf = 1000000000;

int main(){

    ll N,M;
    scanf("%lld%lld",&N,&M);

    vector<vector<ll>> A(N , vector<ll>(N));
    ll ans = inf;

    rep(i,0,N){
        rep(j,0,N){
            scanf("%lld",&A[i][j]);
        }
    }

    rep(i,0,1<<(N+2)){

        vector<vector<ll>> B(N , vector<ll>(N));
        rep(x,0,N){
            rep(y,0,N){
                B[x][y] = A[x][y];
            }
        }

        ll rem = M;
        ll tmp = 0;

        rep(y,0,N){
            if (((1<<y) & i) > 0){
                rem -= 1;
                rep(x,0,N){
                    tmp += B[x][y];
                    B[x][y] = 0;
                }
            }
        }

        ll yy = N;
        if (((1<<yy) & i) > 0){
            rem -= 1;
            rep(k,0,N){
                tmp += B[k][k];
                B[k][k] = 0;
            }
        }

        yy = N+1;
        if (((1<<yy) & i) > 0){
            rem -= 1;
            rep(k,0,N){
                tmp += B[k][N-k-1];
                B[k][N-k-1] = 0;
            }
        }

        //cout << rem << " " << tmp << endl;
        if (rem <= 0) ans = min(ans,tmp);
        else{
            vector<ll> lis(N,0);
            rep(x,0,N){
                rep(y,0,N){
                    lis[x] += B[x][y];
                }
            }

            sort(lis.begin(),lis.end());
            rep(c,0,rem) tmp += lis[c];
            ans = min(ans , tmp);
        }

    }

    cout << ans << endl;
 
}
0