Submission #705152

#	Time	Username	Problem	Language	Result	Execution time	Memory
705152		esomer	Raisins (IOI09_raisins)	C++17	100 / 100	977 ms	24800 KiB

raisins

#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();
    vector<vector<int>> prefix(n, vector<int>(m, 0));
    for(int i = 0; i < n; i++){
		prefix[i][0] = table[i][0];
		for(int j = 1; j < m; j++){
			prefix[i][j] = prefix[i][j-1] + table[i][j];
		}
	}
    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 = lx; i < rx; i++){
                ans = min(ans, DFS(lx, i, ly, ry) + DFS(i + 1, rx, ly, ry));
            }
            int add = 0;
            for(int i = ly; i <= ry; i++){
				if(i < ry) ans = min(ans, DFS(lx, rx, ly, i) + DFS(lx, rx, i + 1, ry));
                add += prefix[i][rx];
                if(lx > 0) add -= prefix[i][lx - 1];
            }
            ans += add;
            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 / 100