oj.uz

Submission #964341

# Submission time Handle Problem Language Result Execution time Memory
964341 2024-04-16T16:45:10 Z anango Raisins (IOI09_raisins) C++17
100 / 100
 645 ms 55432 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> grid;
vector<vector<int>> pref;
vector<vector<vector<vector<int>>>> dp; //(i,j) and (k,l)
int rect(int a, int b, int c, int d) {
    return pref[c+1][d+1]-pref[c+1][b]-pref[a][d+1]+pref[a][b];
}
signed main() {
    //freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n,m;
    cin >> n >> m;
    int INF=1000000007;
    dp=vector(n,vector(m,vector(n,vector<int>(m,INF))));
    pref=vector(n+1,vector<int>(m+1,0));
    grid=vector(n,vector<int>(m,0));
    for (int i=0; i<n; i++) {
        for (int j=0; j<m; j++) {
            int x;
            cin >> x;
            grid[i][j] = x;
        }
    }

    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            pref[i][j] = pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1]+grid[i-1][j-1];
        }
    }
    for (int wid=0; wid<m; wid++) {
        for (int hei=0; hei<n; hei++) {
            for (int tl=0; tl+hei<n; tl++) {
                for (int tr=0; tr+wid<m; tr++) {
                    int bl=tl+hei;
                    int br=tr+wid;
                    if (wid==0 && hei==0) {
                        dp[tl][tr][bl][br] = 0;
                    }
                    else {
                        int R=rect(tl,tr,bl,br);
                        int ans=INF;
                        for (int hcut=tl; hcut<bl; hcut++) {
                            ans=min(ans,dp[tl][tr][hcut][br]+dp[hcut+1][tr][bl][br]+R);
                        }
                        for (int vcut=tr; vcut<br; vcut++) {
                            ans=min(ans,dp[tl][tr][bl][vcut]+dp[tl][vcut+1][bl][br]+R);
                        }
                        dp[tl][tr][bl][br] = ans;
                    }
                    //cout << tl <<" " << tr << " " << bl <<" " << br << " " << dp[tl][tr][bl][br] << endl;
                }
            }
        }
    }
    cout << dp[0][0][n-1][m-1] << endl;
    
    

}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 432 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 3 ms 2044 KB Output is correct
9 Correct 5 ms 3164 KB Output is correct
10 Correct 7 ms 4148 KB Output is correct
11 Correct 7 ms 3444 KB Output is correct
12 Correct 29 ms 9308 KB Output is correct
13 Correct 70 ms 13916 KB Output is correct
14 Correct 12 ms 5256 KB Output is correct
15 Correct 80 ms 16984 KB Output is correct
16 Correct 6 ms 2396 KB Output is correct
17 Correct 25 ms 7772 KB Output is correct
18 Correct 328 ms 33076 KB Output is correct
19 Correct 537 ms 48524 KB Output is correct
20 Correct 645 ms 55432 KB Output is correct