Submission #402253

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
402253	2021-05-11T13:03:39 Z	Azimjon	Raisins (IOI09_raisins)	C++17	25 / 100	54 ms	336 KB

raisins

// 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);
				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	3 ms	204 KB	Output isn't correct
9	Incorrect	4 ms	204 KB	Output isn't correct
10	Incorrect	5 ms	204 KB	Output isn't correct
11	Incorrect	6 ms	204 KB	Output isn't correct
12	Incorrect	12 ms	332 KB	Output isn't correct
13	Incorrect	16 ms	332 KB	Output isn't correct
14	Incorrect	9 ms	336 KB	Output isn't correct
15	Incorrect	17 ms	332 KB	Output isn't correct
16	Incorrect	3 ms	204 KB	Output isn't correct
17	Incorrect	15 ms	336 KB	Output isn't correct
18	Incorrect	35 ms	332 KB	Output isn't correct
19	Correct	45 ms	332 KB	Output is correct
20	Incorrect	54 ms	332 KB	Output isn't correct