Submission #1214918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214918		tapilyoca	Raisins (IOI09_raisins)	C++20	100 / 100	477 ms	72120 KiB

raisins

/***********************************************
* auth: tapilyoca                              *
* date: 06/09/2025 at 11:11:32                 *
* dots: https://github.com/tapilyoca/dotilyoca * 
***********************************************/

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) cerr << #x << ": " << x << endl;

/***********************************************/

ll n, m;
ll memo[55][55][55][55];
vvll grid;
vvll pref;

inline ll rect_sum(ll ti, ll tj, ll bi, ll bj) {
    ll out = pref[bi][bj];
    if(ti == tj and ti == 0) return out;
    if(ti == 0) return out - pref[bi][tj-1];
    if(tj == 0) return out - pref[ti-1][bj];
    return out - pref[bi][tj-1] - pref[ti-1][bj] + pref[ti-1][tj-1];
}

ll dp(ll ti, ll tj, ll bi, ll bj) {
    // returns ans for rectangle with tl corner at [ti][tj] and br corner at [bi][bj], all inclusive.
    if(memo[ti][tj][bi][bj] != -1) {
        return memo[ti][tj][bi][bj];
    }
    // base case: 1 x 1
    if(ti == bi and tj == bj) {
        return memo[ti][tj][bi][bj] = 0;
    }
    // base case: 1 x 2
    if((bi == ti + 1 and bj == tj) or (bi == ti and bj == tj + 1)) {
        return memo[ti][tj][bi][bj] = grid[ti][tj] + grid[bi][bj];
    }

    ll min_hori = 1e18, min_verti = 1e18;
    
    // checking all horizontal cuts:
    for(int i = ti; i < bi; i++) {
        min_hori = min(min_hori, dp(ti,tj,i,bj) + dp(i+1,tj,bi,bj) + rect_sum(ti,tj,bi,bj));
    }

    // checking all vertical cuts:
    for(int i = tj; i < bj; i++) {
        min_verti = min(min_verti, dp(ti,tj,bi,i) + dp(ti,i+1,bi,bj) + rect_sum(ti,tj,bi,bj));
    }

    return memo[ti][tj][bi][bj] = min(min_hori,min_verti);
}

void solve(){
    cin >> n >> m;

    grid.assign(n, vll(m,0));
    pref.assign(n, vll(m,0));
    memset(memo,-1,sizeof(memo));


    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            pref[i][j] = grid[i][j];
            if(i) pref[i][j] += pref[i-1][j];
            if(j) pref[i][j] += pref[i][j-1];
            if(i and j) pref[i][j] -= pref[i-1][j-1];
        }
    }

    

    cout << dp(0ll,0ll,n-1,m-1) << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;

    while(t--){
        solve();
    }

    return 0;
}

/*

 | 1 | 2 | 3 | 4
0| -------------
 | 5 | 6 | 7 | 8
1| -------------
 | 9 | A | B | C
 -----------------
     0   1   2


*/

• Subtask 1: 100 / 100