oj.uz

Submission #850236

# Submission time Handle Problem Language Result Execution time Memory
850236 2023-09-16T07:50:21 Z Tai_xiu Kronican (COCI16_kronican) C++14
100 / 100
 452 ms 5084 KB 
#include <bits/stdc++.h>

using namespace std;
int n,k,dp[1<<20];
int a[20][20];
void solve()
{
    vector<int>lt;
    fill (dp,dp+(1<<20),1000000000);
    for (int i=0;i<(1<<n);i++){
        if (__builtin_popcount(i)==k)
            lt.push_back(i);
    }
    dp[(1<<n)-1]=0;
    int premask;
    for (int mask=(1<<n)-1;mask>=lt[0];mask--){
        vector<int>tam,tam1;
        for (int j=0;j<n;j++){
            if (((mask>>j)&1)==0)
                tam.push_back(j);
            else
                tam1.push_back(j);
        }
        for (int j:tam){
            premask=mask^(1<<j);
            int mi=1000000000;
            for (int k:tam1){
                mi=min(mi,a[j][k]);
            dp[mask]=min(dp[mask],dp[premask]+mi);
            }
        }
    }
    int kq=1000000000;
    for (int i:lt){
       kq=min(kq,dp[i]);
    }
    cout<<kq;
}
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   cin>>n>>k;
   for (int i=0;i<n;i++){
    for (int j=0;j<n;j++)
        cin>>a[i][j];
   }

   solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4444 KB Output is correct
2 Correct 2 ms 4444 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4440 KB Output is correct
5 Correct 7 ms 4440 KB Output is correct
6 Correct 13 ms 4444 KB Output is correct
7 Correct 25 ms 4440 KB Output is correct
8 Correct 56 ms 4684 KB Output is correct
9 Correct 452 ms 4556 KB Output is correct
10 Correct 446 ms 5084 KB Output is correct