# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1226703 | nanaseyuzuki | Kronican (COCI16_kronican) | C++20 | 305 ms | 4544 KiB |
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int, int>
const int mn = 21, inf = 1e18;
int n, k, a[mn][mn];
int dp[(1 << 20) + 1];
void solve(){
cin >> n >> k;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> a[i][j];
}
}
fill(&dp[0], &dp[0] + ((1 << 20) + 1), inf);
dp[(1 << n) - 1] = 0;
int res = INT_MAX;
for(int mask = (1 << n) - 1; mask >= 0; mask --){
vector <int> cand;
for(int i = 0; i < n; i++){
if(mask & (1 << i)) cand.push_back(i);
}
for(auto i : cand){
int new_mask = mask ^ (1 << i);
for(auto j : cand){
if(i == j) continue;
dp[new_mask] = min(dp[new_mask], dp[mask] + a[i][j]);
}
}
if(__builtin_popcount(mask) <= k) res = min(res, dp[mask]);
}
cout << res;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |