oj.uz

Submission #309875

# Submission time Handle Problem Language Result Execution time Memory
309875 2020-10-04T20:44:02 Z sofapuden Raisins (IOI09_raisins) C++14
100 / 100
 1514 ms 44280 KB 
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> gra;
vector<vector<vector<vector<int>>>> dp(55, vector<vector<vector<int>>>(55, vector<vector<int>> (55, vector<int>(55, 0))));

int find(int x, int xb, int y, int yb){
	if(x == xb-1 && y == yb-1)return 0;
	if(dp[x][xb][y][yb])return dp[x][xb][y][yb];
	int r = INT_MAX;
	for(int i = x+1; i < xb; ++i){
		r = min(r,find(x,i,y,yb)+find(i,xb,y,yb));
	}
	for(int i = y+1; i < yb; ++i){
		r = min(r,find(x,xb,y,i)+find(x,xb,i,yb));
	}
	dp[x][xb][y][yb] = r+gra[xb][yb]+gra[x][y]-gra[xb][y]-gra[x][yb];
	return dp[x][xb][y][yb];
}

int main(){
	int n, m; cin >> n >> m;
	gra.resize(n+1, vector<int>(m+1));
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			cin >> gra[i][j];
		}
	}
	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= m; ++j){
			gra[i][j]+=gra[i-1][j]+gra[i][j-1]-gra[i-1][j-1];
		}
	}
	cout << find(0,n,0,m) << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 44160 KB Output is correct
2 Correct 34 ms 44160 KB Output is correct
3 Correct 34 ms 44152 KB Output is correct
4 Correct 34 ms 44152 KB Output is correct
5 Correct 34 ms 44152 KB Output is correct
6 Correct 34 ms 44280 KB Output is correct
7 Correct 35 ms 44152 KB Output is correct
8 Correct 47 ms 44152 KB Output is correct
9 Correct 65 ms 44280 KB Output is correct
10 Correct 72 ms 44160 KB Output is correct
11 Correct 63 ms 44152 KB Output is correct
12 Correct 166 ms 44224 KB Output is correct
13 Correct 266 ms 44280 KB Output is correct
14 Correct 84 ms 44152 KB Output is correct
15 Correct 324 ms 44152 KB Output is correct
16 Correct 57 ms 44160 KB Output is correct
17 Correct 155 ms 44160 KB Output is correct
18 Correct 828 ms 44280 KB Output is correct
19 Correct 1293 ms 44152 KB Output is correct
20 Correct 1514 ms 44280 KB Output is correct