제출 #402242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
402242		Azimjon	Raisins (IOI09_raisins)	C++17	15 / 100	5066 ms	364 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 x = INF;

		for (int i : {l, r, (l + r) / 2, (l + r) / 2 - 1, (l + r) / 2 + 1}) {
			if (i < l || r < i + 1) continue;
			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);
	// 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: 15 / 100