Submission #798233

#	Time	Username	Problem	Language	Result	Execution time	Memory
798233		HaroldVemeno	Raisins (IOI09_raisins)	C++17	100 / 100	109 ms	13492 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 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 / 100