Submission #798223

#	Time	Username	Problem	Language	Result	Execution time	Memory
798223		HaroldVemeno	Raisins (IOI09_raisins)	C++17	85 / 100	54 ms	39828 KiB

raisins

#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 / 100