Submission #1277382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277382		PieArmy	Netrpeljivost (COI23_netrpeljivost)	C++20	100 / 100	376 ms	33308 KiB

Main

#include<bits/stdc++.h>
using namespace std;
typedef long long l;
l n,t[1<<11][1<<11],i,j,k;
vector<l>d[2];
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			cin>>t[i][j];
		}
	}
	long long ans=2e15;
	d[0].resize(n,0);
	d[1].resize(n,ans);
	for(i=1;i<=n;i++){
		for(j=0;j<n;j++){
			if(i==n){
				ans=min(ans,d[0][j]);
				continue;
			}
			int ls=(i&-i);
			for(k=ls;k<ls*2;k++){
				d[1][j^k]=min(d[1][j^k],d[0][j]+t[j][j^k]);
			}
		}
		swap(d[0],d[1]);
		fill(d[1].begin(),d[1].end(),2e15);
	}
	cout<<ans;
}

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