제출 #1217504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217504		jasonic	Raisins (IOI09_raisins)	C++20	100 / 100	188 ms	60968 KiB

raisins

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

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

ll dp[55][55][55][55]; // thing
ll sum[55][55][55][55]; // thing
ll vals[55][55];

int main() {
    fastIO;
    
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            cin >> vals[i][j];
        }
    }

    for(int xsz = 1; xsz <= m; xsz++) {
        for(int ysz = 1; ysz <= n; ysz++) {
            for(int x = 0; x+xsz-1 < m; x++) {
                for(int y = 0; y+ysz-1 < n; y++) {
                    if(xsz == 1 && ysz == 1) {
                        dp[x][x][y][y] = 0;
                        sum[x][x][y][y] = vals[y][x];
                    } else {
                        int xr = x + xsz - 1;
                        int yr = y + ysz - 1;
                        dp[x][xr][y][yr] = LLONG_MAX;
                        if(xsz > 1) {
                            sum[x][xr][y][yr] = sum[x][x][y][yr] + sum[x+1][xr][y][yr];
                            for(int leftBound = x; leftBound < xr; leftBound++) {
                                dp[x][xr][y][yr] = min(dp[x][xr][y][yr], dp[x][leftBound][y][yr] + dp[leftBound+1][xr][y][yr] + sum[x][xr][y][yr]);
                            }
                        }
                        if(ysz > 1) {
                            sum[x][xr][y][yr] = sum[x][xr][y][y] + sum[x][xr][y+1][yr];
                            for(int leftBound = y; leftBound < yr; leftBound++) {
                                dp[x][xr][y][yr] = min(dp[x][xr][y][yr], dp[x][xr][y][leftBound] + dp[x][xr][leftBound+1][yr] + sum[x][xr][y][yr]);
                            }
                        }
                    }

                    // printf("%d %d %d %d: %d, sum was %d\n", x, x+xsz-1, y, y+ysz-1, dp[x][x+xsz-1][y][y+ysz-1], sum[x][x+xsz-1][y][y+ysz-1]);
                }
            }
        }
    }

    cout << dp[0][m-1][0][n-1];
    
    return 0;
}

• Subtask 1: 100 / 100