oj.uz

Submission #309873

# Submission time Handle Problem Language Result Execution time Memory
309873 2020-10-04T20:43:09 Z sofapuden Raisins (IOI09_raisins) C++14
75 / 100
 1505 ms 89464 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));
	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
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 44152 KB Output is correct
2 Correct 34 ms 44160 KB Output is correct
3 Correct 34 ms 44152 KB Output is correct
4 Runtime error 93 ms 89464 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 36 ms 44156 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Correct 38 ms 44288 KB Output is correct
7 Correct 34 ms 44160 KB Output is correct
8 Correct 47 ms 44152 KB Output is correct
9 Runtime error 61 ms 44152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Correct 72 ms 44160 KB Output is correct
11 Correct 66 ms 44280 KB Output is correct
12 Correct 165 ms 44280 KB Output is correct
13 Correct 258 ms 44160 KB Output is correct
14 Runtime error 87 ms 44152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Correct 317 ms 44280 KB Output is correct
16 Correct 57 ms 44152 KB Output is correct
17 Correct 150 ms 44160 KB Output is correct
18 Correct 818 ms 44280 KB Output is correct
19 Correct 1288 ms 44152 KB Output is correct
20 Runtime error 1505 ms 44280 KB Execution killed with signal 11 (could be triggered by violating memory limits)