Submission #1277380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277380		PieArmy	Netrpeljivost (COI23_netrpeljivost)	C++20	100 / 100	344 ms	49736 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;

int n;
int table[1<<11][1<<11];
ll dp[1<<11][1<<11];

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>table[i][j];
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<n;j++){
			dp[i][j]=2e15;
		}
	}
	ll ans=2e15;
	for(int i=1;i<=n;i++){
		for(int j=0;j<n;j++){
			if(i==n){
				ans=min(ans,dp[i-1][j]);
				continue;
			}
			int ls=(i&-i);
			for(int k=ls;k<ls*2;k++){
				dp[i][j^k]=min(dp[i][j^k],dp[i-1][j]+table[j][j^k]);
			}
		}
	}
	cout<<ans<<endl;
}

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