Submission #1114342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114342		SalihSahin	Netrpeljivost (COI23_netrpeljivost)	C++14	100 / 100	422 ms	101964 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int dp[1<<11][(1<<11)+1];
int d[(1<<11)+1][(1<<11)+1];
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
	int n; cin >> n;
 
	for(int i=0; i<=n; i++){
		for(int j=0; j<n; j++){
			dp[j][i]=1e18;
		}
 
		dp[0][i]=0;
 
	}
	for(int i=0; i<n; i++){
		for(int l=0; l<n; l++)
			cin >> d[i][l];
	}
 
 
	for(int i=1; i<n; i++){
		int c=0, val=i;
		int f=0;
		for(int h=0; h<11; h++){
			if(val&(1<<h)){
				c=h;
				break;
			}
		}
 
		for(int h=c; h<=11; h++){
			f+=(1<<h);
		}
		for(int g=0; g<n; g++){
          int h = g^(1<<c);
          h&=f;
          for(int l=0; l<(1<<c); l++){
            dp[i][h+l]=min(dp[i][h+l], dp[i-1][g]+d[g][h+l]);
          }
		}
	}
 
 
	int mi=1e18;
 
	for(int l=0; l<n; l++) mi=min(mi, dp[n-1][l]);
	cout<<mi;
}

• Subtask 1: 10 / 10
• Subtask 2: 17 / 17
• Subtask 3: 32 / 32
• Subtask 4: 41 / 41