Submission #1214896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214896		countless	Raisins (IOI09_raisins)	C++20	20 / 100	1 ms	328 KiB

raisins

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

vector<vector<ll>> grid, pref;

ll query(int lr, int rr, int lc, int rc) {
    return { 0
        + pref[rr][rc]
        - (lr > 0 ? pref[lr-1][rc] : 0)
        - (lc > 0 ? pref[rr][lc-1] : 0)
        + (lr > 0 and lc > 0 ? pref[lr-1][lc-1] : 0)
    };
}

ll decomp(int lr, int rr, int lc, int rc) {
    ll res = query(lr, rr, lc, rc);
    ll sz = (rr - lr + 1) * (rc - lc + 1);

    if (sz < 2) return 0;

    if (sz > 2) {
        ll mn = LLONG_MAX;
        int lr1, rr1, lc1, rc1, lr2, rr2, lc2, rc2;

        for (int i = lr; i < rr; i++) {
            ll q1 = query(lr, i, lc, rc), q2 = query(i+1, rr, lc, rc);
            ll diff = abs(q1 - q2);

            if (diff < mn) {
                mn = diff;
                lr1 = lr, rr1 = i, lc1 = lc, rc1 = rc;
                lr2 = i+1, rr2 = rr, lc2 = lc, rc2 = rc;
            }
        }

        for (int i = lc; i < rc; i++) {
            ll q1 = query(lr, rr, lc, i), q2 = query(lr, rr, i+1, rc);
            ll diff = abs(q1 - q2);

            if (diff < mn) {
                mn = diff;
                lr1 = lr, rr1 = rr, lc1 = lc, rc1 = i;
                lr2 = lr, rr2 = rr, lc2 = i+1, rc2 = rc;
            }
        }

        res += decomp(lr1, rr1, lc1, rc1);
        res += decomp(lr2, rr2, lc2, rc2);
    }

    return res;
}

void solve() {
    int n, m; cin >> n >> m;
    grid.assign(n, vector<ll>(m));
    pref.assign(n, vector<ll>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    pref = grid;
    for (int i = 1; i < n; i++) pref[i][0] += pref[i-1][0];
    for (int i = 1; i < m; i++) pref[0][i] += pref[0][i-1];

    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            pref[i][j] += pref[i-1][j] + pref[i][j-1] - pref[i-1][j-1];
        }
    }

    cout << decomp(0, n-1, 0, m-1) << endl;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

• Subtask 1: 20 / 100