Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define check(N, A, B) assert((N) >= (A) && (N) <= (B))
- using namespace std;
- const int maxn = 30;
- typedef long long ll;
- int a[maxn][maxn];
- int floor(int x){
- int l = 0, r = x;
- while(l < r){
- int m = l+(r-l)/2;
- if(m*m <= x) l = m+1;
- else r = m;
- }
- if(l*l > x) l--;
- return l;
- }
- int main(){
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- int n, k; cin >> n;
- check(n,1,25);
- for(int i=0;i<n;i++)
- for(int j=0;j<n;j++){
- cin >> a[i][j]; check(a[i][j],0,1e6);
- }
- for(int i=0;i<n;i++){
- assert(a[i][i] == 0);
- for(int j=0;j<n;j++)
- assert(a[i][j] == a[j][i]);
- }
- ll ans = 0;
- for(int i=0;i<(1<<n);i++){
- ll cur = 0;
- for(int j=0;j<n;j++)
- if(i&(1<<j)) for(int k=0;k<j;k++)
- if(i&(1<<k)) cur += a[j][k];
- // cout << i << ": " << cur << endl;
- ans += cur * floor(__builtin_popcount(i));
- }
- cout << ans << "\n";
- }
Add Comment
Please, Sign In to add comment