# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1277381 | PieArmy | Netrpeljivost (COI23_netrpeljivost) | C++20 | 0 ms | 0 KiB |
#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,dp[0][j]);
continue;
}
int ls=(i&-i);
for(k=ls;k<ls*2;k++){
dp[1][j^k]=min(dp[1][j^k],dp[0][j]+table[j][j^k]);
}
}
swap(dp[0],dp[1]);
fill(dp[1].begin(),dp[1].end(),2e15);
}
cout<<ans;
}