This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int inf = 1e18 + 7;
void solve(){
int n;
cin >> n;
int m = __lg(n);
int cost[n][n];
for(int i = 0;i<n;i++)for(int j = 0;j<n;j++)cin >> cost[i][j];
vector<vector<vector<vector<int>>>> dp;
dp.resize(m+1);
for(int i = 1;i<=m;i++){
dp[i].resize(n / (1ll << i));
for(int j = 0;j<sz(dp[i]);j++){
dp[i][j].resize(1ll << (i-1));
for(int k = 0;k<sz(dp[i][j]);k++){
dp[i][j][k].assign(1ll << (i-1) , inf);
}
}
}
for(int i = 0;i<n/2;i++){
// 2 lik ler uzerinden tanimla
dp[1][i][0][0] = cost[2 * i][2 * i + 1];
}
// cout << "start" << endl;
for(int i = 1;i<m;i++){
for(int j = 0;j<sz(dp[i]);j+=2){
// cout << "lul : " << i << " , " << j << endl;
for(int t1 = 0;t1<sz(dp[i][j]);t1++)for(int t2 = 0;t2<sz(dp[i][j]);t2++)for(int t3 = 0;t3<sz(dp[i][j]);t3++)for(int t4 = 0;t4<sz(dp[i][j]);t4++){
// cout << "flag0" << endl;
int arr[4];
arr[0] = (1 << i) * j + t1;
arr[1] = (1 << i) * j + (1 << (i-1)) + t2;
arr[2] = (1 << i) * (j + 1) + t3;
arr[3] = (1 << i) * (j + 1) + (1 << (i-1)) + t4;
// cout << "t : " << t1 << " , " << t2 << " , " << t3 << " , " << t4 << endl;
// cout << "arr : " << arr[0] << " , " << arr[1] << " , " << arr[2] << " , " << arr[3] << endl;
// cout << "dp : " << dp[i][j][t1][t2] << " , " << dp[i][j+1][t3][t4] << endl;
// cout << "huh ? " << ((1<<(i-1)) + t4) << " - " << sz(dp[i+1][j/2]) << endl;
// cout << "flag1" << endl;
// 0 2
dp[i+1][j/2][t1][t3] = min(dp[i+1][j/2][t1][t3] , dp[i][j][t1][t2] + dp[i][j+1][t3][t4] + cost[arr[1]][arr[3]]);
// 0 3
dp[i+1][j/2][t1][(1<<(i-1)) + t4] = min(dp[i+1][j/2][t1][(1<<(i-1)) + t4] , dp[i][j][t1][t2] + dp[i][j+1][t3][t4] + cost[arr[1]][arr[2]]);
// 1 2
dp[i+1][j/2][(1<<(i-1)) + t2][t3] = min(dp[i+1][j/2][(1<<(i-1)) + t2][t3] , dp[i][j][t1][t2] + dp[i][j+1][t3][t4] + cost[arr[0]][arr[3]]);
// 1 3
dp[i+1][j/2][(1<<(i-1)) + t2][(1<<(i-1)) + t4] = min(dp[i+1][j/2][(1<<(i-1)) + t2][(1<<(i-1)) + t4] , dp[i][j][t1][t2] + dp[i][j+1][t3][t4] + cost[arr[0]][arr[2]]);
// cout << "flag2" << endl;
}
// cout << "done" << endl;
}
}
int ans = inf;
for(int i = 0;i<sz(dp[m][0]);i++){
for(int j = 0;j<sz(dp[m][0]);j++){
ans = min(ans , dp[m][0][i][j]);
}
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int testcase = 1;//cin >> testcase;
while(testcase--)solve();
cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |