제출 #1226703

#제출 시각아이디문제언어결과실행 시간메모리
1226703nanaseyuzukiKronican (COCI16_kronican)C++20
100 / 100
305 ms4544 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) 메시지

kronican.cpp:6:26: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    6 | const int mn = 21, inf = 1e18;
      |                          ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...