oj.uz

Submission #236273

# Submission time Handle Problem Language Result Execution time Memory
236273 2020-05-31T21:32:08 Z eulerdesoja Kronican (COCI16_kronican) C++14
0 / 100
 1595 ms 33272 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define int long long
typedef pair<int,int>pii;
const int mxN=22,M=1e9+7;
//did u check when n=1?
//is mxN correct?
int n,k,tot;
int tab[mxN][mxN];
int dp[1<<mxN];
int solve(int mask){
    if(dp[mask]!=-1)return dp[mask];
    if(__builtin_popcount(mask)<=k) return dp[mask]=0;
    int ans=M;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!(mask & (1<<i))||!(mask & (1<<j)))continue;
            if(i==j)continue;
            ans=min(ans,solve(mask^(1<<i))+tab[i][j]);
        }
    }
    return dp[mask]=ans;
}
int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp,-1,sizeof(dp));
    cin>>n>>k;
    tot=(1<<n)-1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>tab[i][j];
        }
    }
    cout<<solve(tot);
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Runtime error 21 ms 33144 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
3 Runtime error 22 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
4 Runtime error 22 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Runtime error 31 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 46 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Runtime error 70 ms 33152 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
8 Runtime error 135 ms 33272 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 1595 ms 33220 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 139 ms 33272 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)