Submission #1002349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002349		biximo	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	1447 ms	78388 KiB

Main

#include <bits/stdc++.h>
#define N 2048
// #define INF 
using namespace std;
typedef vector<vector<long long>> vvt;
typedef vector<long long> vt;
int n, cost[N][N];
const long long INF = 1000000000000000000LL;
long long abc[N][N], cda[N][N];
vvt DNC(int x, int y) {
	if(x == y) {
		return {{0}};
	}
	if(x+1 == y) {
		return {{INF,cost[x][y]},{cost[x][y],INF}};
	}
	int z = (x+y)>>1, sze = z-x+1;
	vvt cs1 = DNC(x,z), cs2 = DNC(z+1,y), ans = vvt(y-x+1,vt(y-x+1,INF));
	for(int a = 0; a < sze; a ++) {
		for(int c = 0; c < sze; c ++) {
			long long mv = INF;
			for(int b = 0; b < sze; b ++) {
				mv = min(mv, cs1[a][b]+cost[b+x][c+z+1]);
			}
			for(int d = 0; d < sze; d ++) {
				ans[a][d+sze] = min(ans[a][d+sze], mv+cs2[c][d]);
			}
		}
	}
	for(int i = 0; i < sze; i ++) {
		for(int j = 0; j < sze; j ++) {
			ans[j+sze][i] = ans[i][j+sze];
		}
	}
	return ans;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 0; i < n; i ++) {
		for(int j = 0; j < n; j ++) {
			cin >> cost[i][j];
		}
	}
	vvt lft = DNC(0,n/2-1), rgt = DNC(n/2,n-1);
	vt mv(n,INF);
	for(int i = 0; i < n/2; i ++) {
		for(int j = 0; j < n/2; j ++) {
			mv[i] = min(mv[i], lft[i][j]);
			mv[i+n/2] = min(mv[i+n/2],rgt[i][j]);
		}
	}
	long long fin = INF;
	for(int i = 0; i < n/2; i ++) {
		for(int j = n/2; j < n; j ++) {
			fin = min(fin, mv[i]+mv[j]+cost[i][j]);
		}
	}
	cout << fin;
}

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