oj.uz

답안 #791500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
791500 2023-07-24T07:04:52 Z GEN 이지후(#10078) Nestabilnost (COI23_nestabilnost) C++17
0 / 100
 1500 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXN = 2050;

int n;
int f[MAXN][MAXN];
lint dp[12][MAXN][MAXN];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> f[i][j];
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 0; i < n; i++)
		dp[0][i][i] = 0;
	int lev = 0;
	while ((2 << lev) <= n)
		lev++;
	for (int i = 0; i < lev; i++) {
		for (int j = 0; j < n; j += (2 << i)) {
			int s1 = j, e1 = j + (1 << i);
			int s2 = j + (1 << i), e2 = j + (2 << i);
			for (int k = s1; k < e1; k++) {
				for (int l = s2; l < e2; l++) {
					for (int x = s1; x < e1; x++) {
						for (int y = s2; y < e2; y++) {
							dp[i + 1][k][l] = min(dp[i + 1][k][l], dp[i][k][x] + f[x][y] + dp[i][y][l]);
						}
					}
				}
			}
			for (int k = s1; k < e1; k++) {
				for (int l = s2; l < e2; l++) {
					dp[i + 1][l][k] = dp[i + 1][k][l];
				}
			}
		}
	}
	lint ans = 1e18;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			ans = min(ans, dp[lev][i][j]);
		}
	}
	cout << ans << "\n";
}

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 800 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1569 ms 9180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 138 ms 395068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 800 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 800 ms 524288 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -