Submission #402251

#	Time	Username	Problem	Language	Result	Execution time	Memory
402251		Azimjon	Raisins (IOI09_raisins)	C++17	25 / 100	7 ms	332 KiB

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);
				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 / 100