oj.uz

답안 #798078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
798078 2023-07-30T10:51:19 Z AkramElOmrani 건포도 (IOI09_raisins) C++17
65 / 100
 5000 ms 69664 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll
#define ios ios_base::sync_with_stdio(0);cin.tie(0);

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
 
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int gen(int a, int b) {return (ll)rng() % (b - a + 1) + a;}

const int INF = 1e18L;

signed main()
{
	ios
	int n, m; cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	vector<vector<int>> pref(n + 1, vector<int>(m + 1));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			cin >> a[i][j];
			pref[i + 1][j + 1] += a[i][j];
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= m; ++j) {
			pref[i][j] += pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
		}
	}
	
	// int memo[n][m][n][m];
	vector<vector<vector<vector<int>>>> memo(n, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(n)))); 

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < m; ++j) {
			for(int ii = i; ii < n; ii++)  {
				for(int jj = j; jj < m; ++jj) {
					memo[i][j][ii][jj] = INF;
				}
			}
		}
	}

	function<int(int, int, int, int)> dp = [&](int i, int j, int ii, int jj) {
		if(make_pair(i, j) == make_pair(ii, jj)) return 0LL;
		int& p = memo[i][j][ii][jj];
		if(p != INF) return p;
		int sm = pref[ii + 1][jj + 1]  - pref[i][jj + 1] - pref[ii + 1][j] + pref[i][j];
		// if(sm <= 0) {
			// dbg(i, ii, j, jj, sm)
			// dbg(pref[ii + 1][jj + 1], pref[i][jj + 1], pref[ii + 1][jj], pref[i][j]);
		// }
		int mn = INF;
		for(int f = i; f < ii; ++f) {
			mn = min(mn, dp(i, j, f, jj) + dp(f + 1, j, ii, jj));
		}
		for(int f = j; f < jj; ++f) {
			mn = min(mn, dp(i, j, ii, f) + dp(i, f + 1, ii, jj));
		}
		dbg(mn, sm)
		p = mn + sm;
		return p;
	};
	cout << dp(0, 0, n - 1, m - 1) << '\n';
}

Subtask #1
65.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 11
5 Correct 5 ms 340 KB Output is correct
6 Correct 28 ms 484 KB Output is correct
7 Correct 32 ms 656 KB Output is correct
8 Runtime error 2 ms 3284 KB Execution killed with signal 11
9 Correct 638 ms 5072 KB Output is correct
10 Correct 832 ms 6280 KB Output is correct
11 Runtime error 4 ms 5332 KB Execution killed with signal 11
12 Correct 2134 ms 15664 KB Output is correct
13 Correct 3238 ms 22864 KB Output is correct
14 Runtime error 4 ms 6740 KB Execution killed with signal 11
15 Correct 3819 ms 27304 KB Output is correct
16 Correct 451 ms 7268 KB Output is correct
17 Correct 1677 ms 19048 KB Output is correct
18 Execution timed out 5091 ms 51724 KB Time limit exceeded
19 Execution timed out 5085 ms 63004 KB Time limit exceeded
20 Execution timed out 5075 ms 69664 KB Time limit exceeded