Submission #1215769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215769		ProtonDecay314	Raisins (IOI09_raisins)	C++20	100 / 100	275 ms	29484 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

int main() {

    int n, m;
    cin >> n >> m;

    vvi g(n + 1, vi(m + 1, 0));

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cin >> g[i][j];
            g[i][j] += g[i][j - 1];
            g[i][j] += g[i - 1][j];
            g[i][j] -= g[i - 1][j - 1];
        }
    }

    v4i dp(n, v3i(m, vvi(n, vi(m, INF(int)))));

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

    for(int iw = 0; iw < n; iw++) {
        for(int jw = 0; jw < m; jw++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    int i2 = i + iw, j2 = j + jw;

                    if(i2 >= n || j2 >= m) continue;
                    
                    int& ans = dp[i][j][i2][j2];

                    int cursum = g[i2 + 1][j2 + 1] - g[i][j2 + 1] - g[i2 + 1][j] + g[i][j];
                    
                    /*
                    row cut
                    */

                    for(int k = i; k < i2; k++) {
                        ans = min(ans, dp[k + 1][j][i2][j2] + dp[i][j][k][j2] + cursum);
                    }

                    /*
                    col cut
                    */

                    for(int k = j; k < j2; k++) {
                        ans = min(ans, dp[i][k + 1][i2][j2] + dp[i][j][i2][k] + cursum);
                    }
                }
            }
        }
    }

    cout << dp[0][0][n - 1][m - 1] << endl;

    return 0;
}

• Subtask 1: 100 / 100