# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
831167 | 2023-08-19T20:43:48 Z | gustavo_d | Kronican (COCI16_kronican) | C++17 | 653 ms | 4436 KB |
// 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; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 212 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 6 ms | 340 KB | Output is correct |
6 | Correct | 13 ms | 472 KB | Output is correct |
7 | Correct | 25 ms | 596 KB | Output is correct |
8 | Correct | 57 ms | 852 KB | Output is correct |
9 | Correct | 653 ms | 4436 KB | Output is correct |
10 | Correct | 54 ms | 4436 KB | Output is correct |