oj.uz

Submission #798223

# Submission time Handle Problem Language Result Execution time Memory
798223 2023-07-30T13:46:19 Z HaroldVemeno Raisins (IOI09_raisins) C++17
85 / 100
 54 ms 39828 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 optv[51][51][51][51];
int opth[51][51][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 i = 0; i < m; ++i) {
        for(int j = i+1; j <= m; ++j) {
            for(int k = 0; k < n; ++k) {
                optv[k][k+1][i][j] = k+1;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = i+1; j <= n; ++j) {
            for(int k = 0; k < m; ++k) {
                opth[i][j][k][k+1] = k+1;
            }
        }
    }

    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);

                    int iv = 1 << 30;
                    //int opu = i+1;
                    //int opd = i+vd-1;
                    int opu = max(i+1,    optv[i][i+vd-1][j][j+hd]);
                    int opd = min(i+vd-1, optv[i+1][i+vd][j][j+hd]);
                    D(opu)
                    D(opd)
                    for(int k = opu; k <= opd; ++k) {
                        int nv = val[i][k   ][j][j+hd]
                               + val[k][i+vd][j][j+hd];
                        if(iv > nv) {
                            iv = nv;
                            D(iv)
                            optv[i][i+vd][j][j+hd] = k;
                        }
                    }
                    int jv = 1 << 30;
                    //int opl = j+1;
                    //int opr = j+hd-1;
                    int opl = max(j+1,    opth[i][i+vd][j][j+hd-1]);
                    int opr = min(j+hd-1, opth[i][i+vd][j+1][j+hd]);
                    D(opl)
                    D(opr)
                    for(int k = opl; k <= opr; ++k) {
                        int nv = val[i][i+vd][j][k]
                               + val[i][i+vd][k][j+hd];
                        if(jv > nv) {
                            jv = nv;
                            D(jv)
                            opth[i][i+vd][j][j+hd] = k;
                        }
                    }

                    if(vd == 1) val[i][i+vd][j][j+hd] = tv + jv;
                    else if(hd == 1) val[i][i+vd][j][j+hd] = tv + iv;
                    else 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
85.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct
8 Incorrect 3 ms 4692 KB Output isn't correct
9 Correct 5 ms 7752 KB Output is correct
10 Correct 6 ms 9028 KB Output is correct
11 Correct 4 ms 6484 KB Output is correct
12 Correct 12 ms 16340 KB Output is correct
13 Correct 16 ms 19680 KB Output is correct
14 Incorrect 6 ms 7380 KB Output isn't correct
15 Correct 16 ms 22012 KB Output is correct
16 Incorrect 7 ms 14548 KB Output isn't correct
17 Correct 12 ms 22216 KB Output is correct
18 Correct 35 ms 35056 KB Output is correct
19 Correct 36 ms 36732 KB Output is correct
20 Correct 54 ms 39828 KB Output is correct