oj.uz

Submission #733223

# Submission time Handle Problem Language Result Execution time Memory
733223 2023-04-30T09:22:54 Z penguin133 Raisins (IOI09_raisins) C++17
100 / 100
 292 ms 72044 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int memo[55][55][55][55];
int n, m, A[55][55], P[55][55];

int dp(int x1, int x2, int y1, int y2){
	if(x1 == x2 && y1 == y2)return 0;
	if(memo[x1][x2][y1][y2] != -1)return memo[x1][x2][y1][y2];
	int ans = 1e18;
	for(int i=x1;i<x2;i++){
		ans = min(ans, dp(x1, i, y1, y2) + dp(i+1, x2, y1, y2));
	}
	for(int i=y1;i<y2;i++){
		ans = min(ans, dp(x1, x2, y1, i) + dp(x1, x2, i+1, y2));
	}
	return memo[x1][x2][y1][y2] = ans + (P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]);
}

void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin >> A[i][j], P[i][j] = P[i-1][j] + P[i][j-1] + A[i][j] - P[i-1][j-1];
	memset(memo, -1, sizeof(memo));
	cout << dp(1, n, 1, m) << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

raisins.cpp:37:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   37 | main(){
      | ^~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 71876 KB Output is correct
2 Correct 29 ms 71824 KB Output is correct
3 Correct 28 ms 71908 KB Output is correct
4 Correct 33 ms 71928 KB Output is correct
5 Correct 36 ms 71928 KB Output is correct
6 Correct 35 ms 71896 KB Output is correct
7 Correct 30 ms 71916 KB Output is correct
8 Correct 37 ms 71884 KB Output is correct
9 Correct 41 ms 71920 KB Output is correct
10 Correct 42 ms 72044 KB Output is correct
11 Correct 36 ms 71924 KB Output is correct
12 Correct 53 ms 71880 KB Output is correct
13 Correct 80 ms 71984 KB Output is correct
14 Correct 40 ms 71876 KB Output is correct
15 Correct 75 ms 71988 KB Output is correct
16 Correct 37 ms 71944 KB Output is correct
17 Correct 44 ms 71916 KB Output is correct
18 Correct 165 ms 71992 KB Output is correct
19 Correct 249 ms 71996 KB Output is correct
20 Correct 292 ms 71884 KB Output is correct