oj.uz

Submission #402251

# Submission time Handle Problem Language Result Execution time Memory
402251 2021-05-11T13:02:15 Z Azimjon Raisins (IOI09_raisins) C++17
25 / 100
 7 ms 332 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 yi = 0, py = 0;
		for (int i = l; i <= r; i++)
			yi += sy[i];

		int x = INF;
		vector<int> v;
		for (int i = l; i <= r; i++) {
			py += sy[i];

			if (py > yi - py) {
				v.push_back(i);
				v.push_back(i - 1);
				break;
			}
		}

		for (int i : v) {
			// cerr << i << endl;
			if (i < l || r < i + 1) continue;
			x = min(x, dfs(l, i) + dfs(i + 1, r));
		}

		return x + yi;
	};

	int nt = dfs(0, n - 1);
	// cerr << nt << endl;

	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
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Correct 1 ms 204 KB Output is correct
5 Incorrect 1 ms 204 KB Output isn't correct
6 Correct 1 ms 204 KB Output is correct
7 Incorrect 1 ms 204 KB Output isn't correct
8 Incorrect 1 ms 204 KB Output isn't correct
9 Incorrect 1 ms 204 KB Output isn't correct
10 Incorrect 2 ms 204 KB Output isn't correct
11 Incorrect 2 ms 204 KB Output isn't correct
12 Incorrect 2 ms 332 KB Output isn't correct
13 Incorrect 3 ms 332 KB Output isn't correct
14 Incorrect 2 ms 332 KB Output isn't correct
15 Incorrect 3 ms 332 KB Output isn't correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Incorrect 2 ms 332 KB Output isn't correct
18 Incorrect 5 ms 332 KB Output isn't correct
19 Correct 6 ms 332 KB Output is correct
20 Incorrect 7 ms 332 KB Output isn't correct