Submission #402255

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
402255	2021-05-11T13:04:28 Z	Azimjon	Raisins (IOI09_raisins)	C++17	25 / 100	280 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);
				v.push_back(i - 2);
				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	2 ms	204 KB	Output is correct
7	Incorrect	1 ms	204 KB	Output isn't correct
8	Incorrect	11 ms	324 KB	Output isn't correct
9	Incorrect	12 ms	324 KB	Output isn't correct
10	Incorrect	18 ms	204 KB	Output isn't correct
11	Incorrect	32 ms	204 KB	Output isn't correct
12	Incorrect	48 ms	324 KB	Output isn't correct
13	Incorrect	66 ms	204 KB	Output isn't correct
14	Incorrect	36 ms	332 KB	Output isn't correct
15	Incorrect	71 ms	332 KB	Output isn't correct
16	Incorrect	7 ms	204 KB	Output isn't correct
17	Incorrect	67 ms	332 KB	Output isn't correct
18	Incorrect	202 ms	332 KB	Output isn't correct
19	Correct	242 ms	332 KB	Output is correct
20	Incorrect	280 ms	336 KB	Output isn't correct