제출 #696576

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

raisins

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long ll;
const int MAX = 52;
const int INF = 0x3f3f3f3f;

int n, m, p[MAX][MAX], ps[MAX][MAX], dp[MAX][MAX][MAX][MAX];

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

int solve(int x1, int y1, int x2, int y2){
    if(x1 == x2 && y1 == y2) return 0;
    if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];

    int resp = INF;

    for(int i = x1; i < x2; i++)
        resp = min(resp, solve(x1, y1, i, y2) + solve(i + 1, y1, x2, y2));

    for(int i = y1; i < y2; i++)
        resp = min(resp, solve(x1, y1, x2, i) + solve(x1, i + 1, x2, y2));

    return dp[x1][y1][x2][y2] = resp + getCost(x1, y1, x2, y2);
}

int32_t main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    
    cin >> n >> m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> p[i][j]; 
            ps[i][j] = ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1] + p[i][j];
        }
    }

    memset(dp, -1, sizeof(dp));

    cout << solve(1, 1, n, m) << '\n';
} 

• Subtask 1: 100 / 100