oj.uz

Submission #630888

# Submission time Handle Problem Language Result Execution time Memory
630888 2022-08-17T10:01:49 Z inksamurai Pohlepko (COCI16_pohlepko) C++17
0 / 80
 1000 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3phCa4T ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e

signed main(){
_3phCa4T;
	int n,k;
	cin>>n>>k;
	vec(vi) tbl(n,vi(n));
	rep(i,n){
		rep(j,n){
			cin>>tbl[i][j];
		}
	}
	const int pun=1<<n;
	vi dp(pun,1e9);
	dp[pun-1]=0;
	per(msk,pun){
		rep(i,n){
			if(msk>>i&1){
				int w=1e9;
				rep(j,n){
					if((msk>>j&1)and(j!=i)){
						w=min(w,dp[msk]+tbl[i][j]);
					}
				}
				// print(w);
				dp[msk^(1<<i)]=min(dp[msk^(1<<i)],w);
			}
		}
	}
	int res=1e9;
	rep(msk,pun){
		if(__builtin_popcount(msk)<=k){
			// print(msk,dp[msk]);
			res=min(res,dp[msk]);
		}
	}
	print(res);
}

Subtask #1
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Execution timed out 1074 ms 17748 KB Time limit exceeded
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 2 ms 212 KB Output isn't correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Runtime error 33 ms 65536 KB Execution killed with signal 9
7 Runtime error 46 ms 65536 KB Execution killed with signal 9
8 Execution timed out 1086 ms 16316 KB Time limit exceeded
9 Incorrect 1 ms 340 KB Output isn't correct
10 Incorrect 11 ms 504 KB Output isn't correct
11 Runtime error 35 ms 65536 KB Execution killed with signal 9
12 Incorrect 47 ms 4308 KB Output isn't correct
13 Execution timed out 1082 ms 16224 KB Time limit exceeded
14 Execution timed out 1086 ms 16204 KB Time limit exceeded
15 Incorrect 1 ms 340 KB Output isn't correct
16 Runtime error 51 ms 65536 KB Execution killed with signal 9