제출 #221234

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
221234		tatyam	건포도 (IOI09_raisins)	C++17	100 / 100	315 ms	25976 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned;
#define name3(a,b,c,d,...) d
#define rep1(b) for(int i = 0; i < b; i++)
#define rep2(i,b) for(int i = 0; i < b; i++)
#define rep3(i,a,b) for(int i = a; i < b; i++)
#define rep(...) name3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
#define all(a) begin(a), end(a)
template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    uint a[51][51] = {};
    rep(n) rep(j, m) cin >> a[i + 1][j + 1];
    rep(n + 1) rep(j, m) a[i][j + 1] += a[i][j];
    rep(j, m + 1) rep(n) a[i + 1][j] += a[i][j];
    static uint dp[50][50][51][51];
    memset(dp, 0xff, sizeof(dp));
    rep(50) rep(j, 50) dp[i][j][i + 1][j + 1] = 0;
    rep(x, 1, n + 1) rep(y, 1, m + 1) if(x != 1 || y != 1){
        rep(x1, n - x + 1){
            int x2 = x1 + x;
            rep(y1, m - y + 1){
                int y2 = y1 + y;
                rep(x3, x1 + 1, x2) chmin(dp[x1][y1][x2][y2], dp[x1][y1][x3][y2] + dp[x3][y1][x2][y2]);
                rep(y3, y1 + 1, y2) chmin(dp[x1][y1][x2][y2], dp[x1][y1][x2][y3] + dp[x1][y3][x2][y2]);
                dp[x1][y1][x2][y2] += a[x2][y2] + a[x1][y1] - a[x1][y2] - a[x2][y1];
            }
        }
    }
    cout << dp[0][0][n][m] << endl;
}

• Subtask 1: 100 / 100