제출 #831167

#제출 시각아이디문제언어결과실행 시간메모리
831167gustavo_dKronican (COCI16_kronican)C++17
100 / 100
653 ms4436 KiB
// https://oj.uz/problem/view/COCI16_kronican > p90 #include <bits/stdc++.h> using namespace std; const int maxn = 20; int c[maxn][maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, k; cin >> n >> k; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { cin >> c[i][j]; } } vector<int> dp((1<<n), 1e9); int mn = 1e9; for (int m=0; m<(1 << n); m++) { int mask = m; int qtd = 0; // active bits while ((mask & -mask) != 0) { qtd++; mask -= (mask & -mask); } mask = m; if (qtd <= k) { dp[mask] = 0; } else { for (int i=0; i<n; i++) { if (((1 << i) & mask) != 0) { // ativo (veremos antes dele) for (int j=0; j<n; j++) { if (i != j and ((mask & (1 << j)) != 0)) { // o que receberá água precisa estar ativo dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + c[i][j]); } } } } } } cout << dp[(1<<n) - 1] << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

kronican.cpp: In function 'int main()':
kronican.cpp:18:9: warning: unused variable 'mn' [-Wunused-variable]
   18 |     int mn = 1e9;
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...