Submission #698145

#	Time	Username	Problem	Language	Result	Execution time	Memory
698145		europium	Raisins (IOI09_raisins)	C++17	80 / 100	5061 ms	30740 KiB

raisins

// - 12/2/23
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <cmath>
#include <iterator>
#include <set>
#include <map>
#include <math.h>
#include <iomanip>
#include <unordered_set>
#include <queue>
#include <climits>
using namespace std;
// clang++ -std=c++17 IOI09_Raisins.cpp && ./a.out

using ll = long long;
int n, m;
vector<vector<int>> grid, pref;
map<tuple<int,int,int,int>,int> dp;

int sum(int x1, int y1, int x2, int y2){
    x2++;
    y2++;
    return pref[x2][y2] - pref[x2][y1] - pref[x1][y2] + pref[x1][y1];
}

int get(int x1, int y1, int x2, int y2){
    if (dp.count({x1, y1, x2, y2}) == 1) return dp[{x1, y1, x2, y2}];
    if (x1 == x2 && y1 == y2) return 0;

    int res = INT_MAX;

    // horizontal cuts
    for (int i = x1; i < x2; i++){
        res = min(res, get(x1, y1, i, y2) + get(i + 1, y1, x2, y2) + sum(x1, y1, i, y2) + sum(i + 1, y1, x2, y2));
    }

    // vertical cuts
    for (int j = y1; j < y2; j++){
        res = min(res, get(x1, y1, x2, j) + get(x1, j + 1, x2, y2) + sum(x1, y1, x2, j) + sum(x1, j + 1, x2, y2));
    }

    dp[{x1, y1, x2, y2}] = res;

    // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << res << '\n';
    return res;
}

void solve(){
    cin >> n >> m;

    grid.resize(n, vector<int> (m));
    pref.resize(n + 1, vector<int> (m + 1));

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

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

    // for (int i = 0; i <= n; i++){
    //     for (int j = 0; j <= m; j++) cout << pref[i][j] << ' ';
    //     cout << '\n';
    // }

    cout << get(0, 0, n - 1, m - 1);
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen("input.txt", "r", stdin);
    solve();

    return 0;
}

• Subtask 1: 80 / 100