Submission #402242

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
402242	2021-05-11T12:57:28 Z	Azimjon	Raisins (IOI09_raisins)	C++17	15 / 100	5000 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, (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.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	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	51 ms	204 KB	Output isn't correct
9	Incorrect	39 ms	204 KB	Output isn't correct
10	Incorrect	79 ms	304 KB	Output isn't correct
11	Incorrect	138 ms	204 KB	Output isn't correct
12	Incorrect	333 ms	332 KB	Output isn't correct
13	Incorrect	688 ms	332 KB	Output isn't correct
14	Incorrect	349 ms	332 KB	Output isn't correct
15	Incorrect	865 ms	332 KB	Output isn't correct
16	Incorrect	39 ms	204 KB	Output isn't correct
17	Incorrect	106 ms	332 KB	Output isn't correct
18	Incorrect	2428 ms	336 KB	Output isn't correct
19	Execution timed out	5066 ms	364 KB	Time limit exceeded
20	Execution timed out	5050 ms	332 KB	Time limit exceeded