結果
| 問題 | No.1345 Beautiful BINGO |
| ユーザー |
 tada721
|
| 提出日時 | 2021-01-16 14:35:27 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 9,702 bytes |
| コンパイル時間 | 613 ms |
| コンパイル使用メモリ | 78,076 KB |
| 最終ジャッジ日時 | 2024-11-14 23:58:37 |
| 合計ジャッジ時間 | 1,250 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:213:19: error: 'numeric_limits' was not declared in this scope
213 | const T INF = numeric_limits<T>::max();
| ^~~~~~~~~~~~~~
main.cpp:213:35: error: expected primary-expression before '>' token
213 | const T INF = numeric_limits<T>::max();
| ^
main.cpp:213:41: error: too few arguments to function 'long long int max(long long int, long long int)'
213 | const T INF = numeric_limits<T>::max();
| ~~~~~^~
main.cpp:83:5: note: declared here
83 | int max(int a, int b) {
| ^~~
main.cpp: In function 'long long int keta(long long int)':
main.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
40 | }
| ^
main.cpp: In function 'long long int gcd(long long int, long long int)':
main.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
54 | }
| ^
main.cpp: In function 'long long int lcm(long long int, long long int)':
main.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
67 | }
| ^
ソースコード
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
#include<queue>
#include<math.h>
#include<deque>
#include<set>
#include<bitset>
using namespace std;
#define double long double
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define dc(d) double d;cin>>d;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
#define pi 3.141592653589793238462643383279
#define e_ 2.718281828459045235360287471352
#define P pair<int,int>
#define upp(a,n,x) upper_bound(a,a+n,x)-a;
#define low(a,n,x) lower_bound(a,a+n,x)-a;
#define pb push_back
//printf("%.12Lf\n",);
int keta(int x) {
rep(0, i, 30) {
if (x < 10) {
return i + 1;
}
x = x / 10;
}
}
int gcd(int x, int y) {
if (x == 0 || y == 0)return x + y;
int aa = x, bb = y;
rep(0, i, 1000) {
aa = aa % bb;
if (aa == 0) {
return bb;
}
bb = bb % aa;
if (bb == 0) {
return aa;
}
}
}
int lcm(int x, int y) {
int aa = x, bb = y;
rep(0, i, 1000) {
aa = aa % bb;
if (aa == 0) {
return x / bb * y;
}
bb = bb % aa;
if (bb == 0) {
return x / aa * y;
}
}
}
int integer(double d){
return long(d);
}
int distance(double a,double b,double c,double d){
return sqrt((b-a)*(b-a)+(c-d)*(c-d));
}
bool prime(int x) {
if (x == 1)return false;
rep(2, i, sqrt(x) + 1) {
if (x % i == 0 && x != i) {
return false;
}
}
return true;
}
int max(int a, int b) {
if (a >= b)return a;
else return b;
}
string maxst(string s, string t) {
int n = s.size();
int m = t.size();
if (n > m)return s;
else if (n < m)return t;
else {
rep(0, i, n) {
if (s[i] > t[i])return s;
if (s[i] < t[i])return t;
}
return s;
}
}
int min(int a, int b) {
if (a >= b)return b;
else return a;
}
string string_reverse(string s){
int n=s.size();
string t;
rep(0,i,n)t+=s[n-i-1];
return t;
}
int newcom(int n,int y){
int bunsi = 1, bunbo = 1;
rep(0, i, y){
bunsi = (bunsi * (n - i)) ;
bunbo = (bunbo * (i + 1)) ;
int k=gcd(bunsi,bunbo);
bunsi/=k;
bunbo/=k;
}
return bunsi/bunbo;
}
int yakuwa(int n) {
int sum = 0;
rep(1, i, sqrt(n + 1)) {
if (n % i == 0)sum += i + n / i;
if (i * i == n)sum -= i;
}
return sum;
}
int poow(int n,int m){
int pro=1;
int nn=n;
while(m){
if(m%2==1)pro=pro*nn%mod;
m=m/2;
nn=nn*nn%mod;
}
return pro;
}
int inv(int n,int m){
int t=poow(m,mod-2)%mod;
return n*t%mod;
}
int com(int n,int m){
int bunsi=1,bunbo=1;
for(int i=n-m+1;i<=n;i++)bunsi=bunsi*i%mod;
for(int i=1;i<=m;i++)bunbo=bunbo*i%mod;
return inv(bunsi,bunbo);
}
int minpow(int x, int y) {
int sum = 1;
rep(0, i, y)sum *= x;
return sum;
}
int ketawa(int x, int sinsuu) {
int sum = 0;
rep(0, i, 100)sum += (x % minpow(sinsuu, i + 1)) / (minpow(sinsuu, i));
return sum;
}
int sankaku(int a) {
if(a%2==0) return a /2*(a+1);
else return (a+1)/2*a;
}
int sames(int a[1111111], int n) {
int ans = 0;
rep(0, i, n) {
if (a[i] == a[i + 1]) {
int j = i;
while (a[j + 1] == a[i] && j <= n - 2)j++;
ans += sankaku(j - i);
i = j;
}
}
return ans;
}
using Graph = vector<vector<int>>;
int oya[214514];
int depth[214514];
void dfs(const Graph& G, int v, int p, int d) {
depth[v] = d;
oya[v] = p;
for (auto nv : G[v]) {
if (nv == p) continue; // nv が親 p だったらダメ
dfs(G, nv, v, d + 1); // d を 1 増やして子ノードへ
}
}
struct UnionFind {
vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2
UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
for (int i = 0; i < N; i++) par[i] = i;
}
int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(int x, int y) { // xとyの木を併合
int rx = root(x); //xの根をrx
int ry = root(y); //yの根をry
if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
}
bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
int rx = root(x);
int ry = root(y);
return rx == ry;
}
};
template <typename T>
struct RMQ {
const T INF = numeric_limits<T>::max();
int n;
vector<T> dat, lazy;
RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, INF) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
/* lazy eval */
void eval(int k) {
if (lazy[k] == INF) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
lazy[k * 2 + 1] = min(dat[k],lazy[k]);
lazy[k * 2 + 2] = min(dat[k],lazy[k]);
}
// 自身を更新
dat[k] = min(dat[k],lazy[k]);
lazy[k] = INF;
}
void update(int a, int b, T x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { // 完全に内側の時
lazy[k] = x;
eval(k);
} else if (a < r && l < b) { // 一部区間が被る時
update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void update(int a, int b, T x) { update(a, b, x, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { // 完全に外側の時
return INF;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
/* debug */
inline T operator[](int a) { return query(a, a + 1); }
void print() {
for (int i = 0; i < 2 * n - 1; ++i) {
cout << (*this)[i];
if (i != n) cout << ",";
}
cout << endl;
}
T max_v[1114514], smax_v[1114514];
T sum[1114514], max_c[1114514];
void update_node_max(int k, T x) {
sum[k] += (x - max_v[k]) * max_c[k];
max_v[k] = x;
}
void push(int k) {
if(max_v[k] < max_v[2*k+1]) {
update_node_max(2*k+1, max_v[k]);
}
if(max_v[k] < max_v[2*k+2]) {
update_node_max(2*k+2, max_v[k]);
}
}
void update(int k) {
sum[k] = sum[2*k+1] + sum[2*k+2];
if(max_v[2*k+1] < max_v[2*k+2]) {
max_v[k] = max_v[2*k+2];
max_c[k] = max_c[2*k+2];
smax_v[k] = max(max_v[2*k+1], smax_v[2*k+2]);
} else if(max_v[2*k+1] > max_v[2*k+2]) {
max_v[k] = max_v[2*k+1];
max_c[k] = max_c[2*k+1];
smax_v[k] = max(smax_v[2*k+1], max_v[2*k+2]);
} else {
max_v[k] = max_v[2*k+1];
max_c[k] = max_c[2*k+1] + max_c[2*k+2];
smax_v[k] = max(smax_v[2*k+1], smax_v[2*k+2]);
}
}
void _update_min(T x, int a, int b, int k, int l, int r) {
if(b <= l || r <= a || max_v[k] <= x) {
return;
}
if(a <= l && r <= b && smax_v[k] < x) {
update_node_max(k, x);
return;
}
push(k);
_update_min(x, a, b, 2*k+1, l, (l+r)/2);
_update_min(x, a, b, 2*k+2, (l+r)/2, r);
update(k);
}
T _query_max(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return 0;
}
if(a <= l && r <= b) {
return max_v[k];
}
push(k);
T lv = _query_max(a, b, 2*k+1, l, (l+r)/2);
T rv = _query_max(a, b, 2*k+2, (l+r)/2, r);
return max(lv, rv);
}
T _query_sum(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) {
return 0;
}
if(a <= l && r <= b) {
return sum[k];
}
push(k);
T lv = _query_sum(a, b, 2*k+1, l, (l+r)/2);
T rv = _query_sum(a, b, 2*k+2, (l+r)/2, r);
return lv + rv;
}
};
int a[20][20];
signed main(){
ic(n) ic(m)
int s=0;
rep(0,i,n)rep(0,j,n){
cin>>a[i][j];
s+=a[i][j];
}
if(m>=n*2+1){
c(s)
return 0;
}
int ans=inf;
rep(0,q,1<<n){
int t=q;
int b[25];
int k=0;
rep(0,i,n){
b[i]=t%2;
k+=b[i];
t=t/2;
}
int sum=0;
int l[25];
rep(0,i,n)l[i]=0;
rep(0,i,n)rep(0,j,n){
if(b[i])sum+=a[i][j];
else l[j]+=a[i][j];
}
sort(l,l+n);
if(m-k<=n){
rep(0,i,m-k)sum+=l[i];
ans=min(ans,sum);
}
}
rep(0,q,1<<n){
int t=q;
int b[25];
int k=1;
rep(0,i,n){
b[i]=t%2;
k+=b[i];
t=t/2;
}
int sum=0;
int l[25];
rep(0,i,n)l[i]=0;
rep(0,i,n)rep(0,j,n){
if(i==j)sum+=a[i][j];
else if(b[i])sum+=a[i][j];
else l[j]+=a[i][j];
}
sort(l,l+n);
if(m-k<=n){
rep(0,i,m-k)sum+=l[i];
ans=min(ans,sum);
}
}
rep(0,q,1<<n){
int t=q;
int b[25];
int k=1;
rep(0,i,n){
b[i]=t%2;
k+=b[i];
t=t/2;
}
int sum=0;
int l[25];
rep(0,i,n)l[i]=0;
rep(0,i,n)rep(0,j,n){
if(i+j==n-1)sum+=a[i][j];
else if(b[i])sum+=a[i][j];
else l[j]+=a[i][j];
}
sort(l,l+n);
if(m-k<=n){
rep(0,i,m-k)sum+=l[i];
ans=min(ans,sum);
}
}
rep(0,q,1<<n){
int t=q;
int b[25];
int k=2;
rep(0,i,n){
b[i]=t%2;
k+=b[i];
t=t/2;
}
int sum=0;
int l[25];
rep(0,i,n)l[i]=0;
rep(0,i,n)rep(0,j,n){
if(i==j||i+j==n-1)sum+=a[i][j];
else if(b[i])sum+=a[i][j];
else l[j]+=a[i][j];
}
sort(l,l+n);
if(m-k<=n){
rep(0,i,m-k)sum+=l[i];
ans=min(ans,sum);
}
}
c(ans)
}