oj.uz

답안 #317320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
317320 2020-10-29T12:54:39 Z fadi57 Kronican (COCI16_kronican) C++14
100 / 100
 1435 ms 8704 KB 
#include <bits/stdc++.h>
using namespace std;
const long long mx=21;
const long long mod=1e9+7;
typedef long long ll;
int a[mx][mx];
int dp[1<<mx];int k;int n,m;
int solve(int mask){
     if (__builtin_popcount(mask) == k) return 0;
     int &ret=dp[mask];
    
     if(ret!=-1){return ret;}
     ret=1<<30;
     for(int i=0;i<n;i++){
         if(!(mask&(1<<i))){continue;}
         for(int j=0;j<n;j++){
             if(i==j){continue;}
              if(!(mask&(1<<j))){continue;}
           
                  ret=min(ret,solve(mask^(1<<i))+a[i][j]);
         }
     }
    return ret;
    
    
}



int main() { 
memset(dp,-1,sizeof(dp));
cin>>n>>k;
for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
    cin>>a[i][j];//cout<<a[i][j];
        
    }
}
cout<<solve((1<<n)-1);

}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8576 KB Output is correct
2 Correct 5 ms 8576 KB Output is correct
3 Correct 5 ms 8576 KB Output is correct
4 Correct 5 ms 8704 KB Output is correct
5 Correct 15 ms 8576 KB Output is correct
6 Correct 28 ms 8576 KB Output is correct
7 Correct 53 ms 8572 KB Output is correct
8 Correct 115 ms 8696 KB Output is correct
9 Correct 1435 ms 8696 KB Output is correct
10 Correct 127 ms 8568 KB Output is correct