Submission #1002173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1002173		biximo	Netrpeljivost (COI23_netrpeljivost)	C++17	59 / 100	1509 ms	77996 KiB

Main

#include <bits/stdc++.h>
#define N 2048
#define INF 1000000000000000000LL
using namespace std;
typedef vector<vector<long long>> vvt;
typedef vector<long long> vt;
int n, cost[N][N];
long long abc[N][N], cda[N][N];
vvt DNC(int x, int y) {
	if(x == y) {
		vvt res = vvt(1,vt(1,0));
		return res;
	}
	int z = (x+y)>>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 <= z-x; a ++) {
		for(int c = 0; c <= z-x; c ++) {
			abc[a][c] = INF;
			for(int b = 0; b <= z-x; b ++) {
				abc[a][c] = min(abc[a][c], cs1[a][b]+cost[b+x][c+z+1]);
			}
		}
	}
	for(int c = 0; c <= z-x; c ++) {
		for(int a = 0; a <= z-x; a ++) {
			cda[c][a] = INF;
			for(int d = 0; d <= z-x; d ++) {
				cda[c][a] = min(cda[c][a], cs2[c][d]+cost[d+z+1][a+x]);
			}
		}
	}
	for(int a = 0; a <= z-x; a ++) {
			for(int d = 0; d <= z-x; d ++) {
		for(int c = 0; c <= z-x; c ++) {
				ans[a][d+(z-x+1)] = min(ans[a][d+(z-x+1)], abc[a][c]+cs2[c][d]);
			}
		}
	}
	for(int c = 0; c <= z-x; c ++) {
			for(int b = 0; b <= z-x; b ++) {
		for(int a = 0; a <= z-x; a ++) {
				ans[c+(z-x+1)][b] = min(ans[c+(z-x+1)][b], cda[c][a]+cs1[a][b]);
			}
		}
	}
	// cout << "OK!\n";
	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 ans = DNC(0,n-1);
	long long fin = INF;
	for(int i = 0; i < n; i ++) {
		fin = min(fin, *min_element(ans[i].begin(),ans[i].end()));
	}
	cout << fin;
}

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