Submission #1114166

#TimeUsernameProblemLanguageResultExecution timeMemory
1114166NotLinuxNetrpeljivost (COI23_netrpeljivost)C++17
59 / 100
1541 ms90340 KiB
// 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...