oj.uz

답안 #402231

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402231 2021-05-11T12:50:48 Z Azimjon 건포도 (IOI09_raisins) C++17
20 / 100
 5000 ms 388 KB 
// Muallif: Azimjon Mehmonali o'g'li

#include <bits/stdc++.h>

using namespace std;

#define int long long

const long double PI = 3.1415926535897;
const int mod = 1000000007LL;
const int INF = 1e18;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	vector<vector<int>> g(n, vector<int>(m));
	vector<int> sy;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> g[i][j];
		}
		sy.push_back(accumulate(g[i].begin(), g[i].end(), 0));
	}

	vector<vector<int>> dp(n, vector<int>(n, INF));

	function<int(int, int)> dfs = [&](int l, int r) {
		if (l == r) return 0ll;

		if (dp[l][r] != INF) return dp[l][r];

		int x = INF;

		for (int i = l; i + 1 <= r; i++) {
			x = min(x, dfs(l, i) + dfs(i + 1, r));
		}

		for (int i = l; i <= r; i++)
			x += sy[i];

		return x;
	};

	int nt = dfs(0, n - 1);

	for (int i = 0; i < n; i++) {
		dp.assign(m, vector<int>(m, INF));
		sy = g[i];

		nt += dfs(0, m - 1);
	}

	cout << nt << endl;

	return 0;
}

Subtask #1
20.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 308 KB Output isn't correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 312 KB Output isn't correct
6 Correct 6 ms 316 KB Output is correct
7 Incorrect 43 ms 316 KB Output isn't correct
8 Execution timed out 5087 ms 300 KB Time limit exceeded
9 Execution timed out 5093 ms 332 KB Time limit exceeded
10 Execution timed out 5083 ms 332 KB Time limit exceeded
11 Execution timed out 5092 ms 204 KB Time limit exceeded
12 Execution timed out 5065 ms 332 KB Time limit exceeded
13 Execution timed out 5084 ms 332 KB Time limit exceeded
14 Execution timed out 5091 ms 204 KB Time limit exceeded
15 Execution timed out 5082 ms 388 KB Time limit exceeded
16 Execution timed out 5095 ms 332 KB Time limit exceeded
17 Execution timed out 5090 ms 332 KB Time limit exceeded
18 Execution timed out 5085 ms 332 KB Time limit exceeded
19 Execution timed out 5089 ms 332 KB Time limit exceeded
20 Execution timed out 5061 ms 332 KB Time limit exceeded