Submission #1114174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114174		NotLinux	Netrpeljivost (COI23_netrpeljivost)	C++17	59 / 100	1555 ms	50168 KiB

Main

// put it before the include
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// Author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const long long inf = 1e18 + 7;
void solve(){
	int n;
	cin >> n;
	int m = __lg(n);
	long long 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<long long>>>> 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;
		}
	}
	long long 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;
}

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