Submission #1286729

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286729		BlockOG	Raisins (IOI09_raisins)	C++20	20 / 100	2 ms	576 KiB

raisins

#include <bits/stdc++.h>

// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = [] {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

int r[51][51];

int do_section(int il, int jl, int ir, int jr) {
    if (ir - il <= 1 && jr - jl <= 1) return 0;

    int mi = INT_MAX;
    int lil, ljl, lir, ljr;
    int ril, rjl, rir, rjr;

    fo(i, il + 1, ir) {
        int d = abs((r[i][jr] - r[i][jl] - r[il][jr] + r[il][jl]) - (r[ir][jr] - r[ir][jl] - r[i][jr] + r[i][jl]));
        if (d < mi) {
            mi = d;
            lil = il, ljl = jl, lir = i, ljr = jr;
            ril = i, rjl = jl, rir = ir, rjr = jr;
        }
    }
    fo(j, jl + 1, jr) {
        int d = abs((r[ir][j] - r[ir][jl] - r[il][j] + r[il][jl]) - (r[ir][jr] - r[ir][j] - r[il][jr] + r[il][j]));
        if (d < mi) {
            mi = d;
            lil = il, ljl = jl, lir = ir, ljr = j;
            ril = il, rjl = j, rir = ir, rjr = jr;
        }
    }

    return r[ir][jr] - r[ir][jl] - r[il][jr] + r[il][jl] + do_section(lil, ljl, lir, ljr) + do_section(ril, rjl, rir, rjr);
}

int main() {
    int n, m; cin >> n >> m;
    fo(i, 0, n) fo(j, 0, m) cin >> r[i + 1][j + 1];
    fo(i, 0, n) fo(j, 1, m) r[i + 1][j + 1] += r[i + 1][j];
    fo(i, 1, n) fo(j, 0, m) r[i + 1][j + 1] += r[i][j + 1];

    cout << do_section(0, 0, n, m);
}

• Subtask 1: 20 / 100