oj.uz

Submission #484447

# Submission time Handle Problem Language Result Execution time Memory
484447 2021-11-03T13:10:13 Z PoPularPlusPlus Raisins (IOI09_raisins) C++17
100 / 100
 185 ms 26828 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

const int N = 51;
int dp[N][N][N][N];
int p[N][N];

int cal(int x1 , int y1 , int x2 , int y2){
	return p[x2][y2] - (x1 > 0 ? p[x1-1][y2] : 0) - (y1 > 0 ? p[x2][y1-1] : 0) + (x1 > 0 && y1 >0 ? p[x1-1][y1-1] : 0);
}

int rec(int x, int y , int x1 , int y1){
	if(x == x1 && y == y1)return 0;
	if(dp[x][y][x1][y1] != -1)return dp[x][y][x1][y1];
	int res = INT_MAX;
	for(int i = x; i < x1; i++){
		res = min(res , rec(x,y,i,y1) + rec(i + 1 , y , x1 , y1));
	}
	for(int j = y; j < y1; j++){
		res = min(res , rec(x,y,x1,j) + rec(x,j + 1 , x1 , y1));
	}
	return dp[x][y][x1][y1] = res + cal(x,y,x1,y1);
}

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

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 26760 KB Output is correct
2 Correct 9 ms 26796 KB Output is correct
3 Correct 9 ms 26700 KB Output is correct
4 Correct 9 ms 26700 KB Output is correct
5 Correct 10 ms 26700 KB Output is correct
6 Correct 10 ms 26700 KB Output is correct
7 Correct 10 ms 26700 KB Output is correct
8 Correct 12 ms 26776 KB Output is correct
9 Correct 13 ms 26700 KB Output is correct
10 Correct 15 ms 26688 KB Output is correct
11 Correct 15 ms 26816 KB Output is correct
12 Correct 27 ms 26700 KB Output is correct
13 Correct 39 ms 26700 KB Output is correct
14 Correct 18 ms 26812 KB Output is correct
15 Correct 44 ms 26700 KB Output is correct
16 Correct 13 ms 26724 KB Output is correct
17 Correct 24 ms 26808 KB Output is correct
18 Correct 100 ms 26812 KB Output is correct
19 Correct 158 ms 26828 KB Output is correct
20 Correct 185 ms 26820 KB Output is correct