Submission #402240

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
402240	2021-05-11T12:56:40 Z	Azimjon	Raisins (IOI09_raisins)	C++17	15 / 100	96 ms	364 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 x = INF;

		for (int i : {l, r, (l + r) / 2}) {
			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.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	Incorrect	1 ms	204 KB	Output isn't correct
5	Incorrect	1 ms	316 KB	Output isn't correct
6	Incorrect	1 ms	204 KB	Output isn't correct
7	Incorrect	3 ms	204 KB	Output isn't correct
8	Incorrect	2 ms	204 KB	Output isn't correct
9	Incorrect	2 ms	204 KB	Output isn't correct
10	Incorrect	3 ms	204 KB	Output isn't correct
11	Incorrect	4 ms	204 KB	Output isn't correct
12	Incorrect	8 ms	340 KB	Output isn't correct
13	Incorrect	15 ms	336 KB	Output isn't correct
14	Incorrect	8 ms	332 KB	Output isn't correct
15	Incorrect	17 ms	344 KB	Output isn't correct
16	Incorrect	2 ms	332 KB	Output isn't correct
17	Incorrect	4 ms	332 KB	Output isn't correct
18	Incorrect	38 ms	336 KB	Output isn't correct
19	Correct	96 ms	364 KB	Output is correct
20	Incorrect	95 ms	332 KB	Output isn't correct