Submission #228667

#	Time	Username	Problem	Language	Result	Execution time	Memory
228667		osaaateiasavtnl	Raisins (IOI09_raisins)	C++14	100 / 100	105 ms	21528 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 52, INF = 1e9 + 7;
int dp[N][N][N][N];
int a[N][N];

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

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            a[i][j] += a[i - 1][j] + a[i][j - 1];
            a[i][j] -= a[i - 1][j - 1];
        }
    for (int x1 = n; x1; --x1) {
        for (int y1 = m; y1; --y1) {
            for (int x2 = x1; x2 <= n; ++x2) {
                for (int y2 = y1; y2 <= m; ++y2) {

                    if (x1 == x2 && y1 == y2) {
                        dp[x1][y1][x2][y2] = 0;
                        continue;
                    }

                    int add = INF;
                    for (int i = x1; i < x2; ++i) {
                        add = min(add, dp[x1][y1][i][y2] + dp[i + 1][y1][x2][y2]);
                    }   
                    for (int i = y1; i < y2; ++i) {
                        add = min(add, dp[x1][y1][x2][i] + dp[x1][i + 1][x2][y2]);
                    }   
                    dp[x1][y1][x2][y2] = add + sum(x1, y1, x2, y2);

                    #ifdef HOME
                    cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << " : " << dp[x1][y1][x2][y2] << endl;
                    #endif
                }   
            }   
        }   
    }
    cout << dp[1][1][n][m] << endl;
}

• Subtask 1: 100 / 100