oj.uz

Submission #705149

# Submission time Handle Problem Language Result Execution time Memory
705149 2023-03-03T12:49:53 Z esomer Raisins (IOI09_raisins) C++17
100 / 100
 1517 ms 24800 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define endl "\n"
 
const int MOD = 1e9 + 7;
 
int dp[50][50][50][50];
 
int solve2(vector<vector<int>>& table){
    int n = table.size();
    int m = table[0].size();
    function<int(int, int, int, int)> DFS = [&](int lx, int rx, int ly, int ry){
        if(rx - lx == 0 && ry - ly == 0) return 0;
        if(dp[lx][rx][ly][ry] == -1){
            int ans = 2e9;
            for(int i = ly; i < ry; i++){
                ans = min(ans, DFS(lx, rx, ly, i) + DFS(lx, rx, i + 1, ry));
            }
            for(int i = lx; i < rx; i++){
                ans = min(ans, DFS(lx, i, ly, ry) + DFS(i + 1, rx, ly, ry));
            }
            for(int i = ly; i <= ry; i++){
                for(int j = lx; j <= rx; j++) ans += table[i][j];
            }
            dp[lx][rx][ly][ry] = ans;
            return (int)ans;
        }else return dp[lx][rx][ly][ry];
    };
    return DFS(0, m - 1, 0, n - 1);
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
 
    //int tt; cin >> tt;
    int n, m; cin >> n >> m;
	vector<vector<int>> table(n, vector<int>(m));
    for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> table[i][j];
		}         
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int q = 0; q < m; q++){
				for(int l = 0; l < n; l++){
					dp[j][q][l][i] = -1;
				}
			}
		}         
	}
	cout << solve2(table)<< endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 464 KB Output is correct
5 Correct 1 ms 456 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 15 ms 4180 KB Output is correct
9 Correct 26 ms 4436 KB Output is correct
10 Correct 42 ms 5844 KB Output is correct
11 Correct 37 ms 6904 KB Output is correct
12 Correct 134 ms 9752 KB Output is correct
13 Correct 210 ms 12384 KB Output is correct
14 Correct 57 ms 9556 KB Output is correct
15 Correct 329 ms 13088 KB Output is correct
16 Correct 17 ms 1496 KB Output is correct
17 Correct 95 ms 4704 KB Output is correct
18 Correct 759 ms 16928 KB Output is correct
19 Correct 1313 ms 24144 KB Output is correct
20 Correct 1517 ms 24800 KB Output is correct