oj.uz

Submission #798233

# Submission time Handle Problem Language Result Execution time Memory
798233 2023-07-30T13:56:08 Z HaroldVemeno Raisins (IOI09_raisins) C++17
100 / 100
 109 ms 13492 KB 
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int tb[50][50];
int tbps[51][51];
int val[51][51][51][51];

int gs(int uly, int ulx, int dry, int drx) {
    return tbps[dry][drx]
         - tbps[uly][drx]
         - tbps[dry][ulx]
         + tbps[uly][ulx];

}

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

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

    for(int vd = 1; vd <= n; ++vd) {
        for(int hd = 1; hd <= m; ++hd) {
            if(vd*hd == 1) continue;
            for(int i = 0; i+vd <= n; ++i) {
                for(int j = 0; j+hd <= m; ++j) {
                    D(i)
                    D(j)
                    D(vd)
                    D(hd)
                    int tv = gs(i,j,i+vd,j+hd);

                    ll iv = 1ll << 40;
                    for(int k = i+1; k <= i+vd-1; ++k) {
                        int nv = val[i][k   ][j][j+hd]
                               + val[k][i+vd][j][j+hd];
                        if(iv > nv) {
                            iv = nv;
                            D(iv)
                        }
                    }
                    ll jv = 1ll << 40;
                    for(int k = j+1; k <= j+hd-1; ++k) {
                        int nv = val[i][i+vd][j][k]
                               + val[i][i+vd][k][j+hd];
                        if(jv > nv) {
                            jv = nv;
                            D(jv)
                        }
                    }

                    val[i][i+vd][j][j+hd] = tv + min(iv, jv);
                }
            }
        }
    }
    cout << val[0][n][0][m] << '\n';

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 596 KB Output is correct
7 Correct 1 ms 980 KB Output is correct
8 Correct 2 ms 1748 KB Output is correct
9 Correct 3 ms 2772 KB Output is correct
10 Correct 4 ms 3156 KB Output is correct
11 Correct 3 ms 2388 KB Output is correct
12 Correct 12 ms 5700 KB Output is correct
13 Correct 19 ms 6708 KB Output is correct
14 Correct 4 ms 2644 KB Output is correct
15 Correct 20 ms 7508 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 10 ms 7636 KB Output is correct
18 Correct 58 ms 11904 KB Output is correct
19 Correct 82 ms 12400 KB Output is correct
20 Correct 109 ms 13492 KB Output is correct