제출 #1227708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227708		lukasuliashvili	Raisins (IOI09_raisins)	C++20	100 / 100	572 ms	53528 KiB

raisins

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pb push_back
#define fs first 
#define sc second 
const int N=52;
int a[N][N],dp[N][N][N][N],pr[N][N];
int cnt(int x1, int x2, int y1, int y2){
    int sum=pr[x2][y2]-pr[x1-1][y2]-pr[x2][y1-1]+pr[x1-1][y1-1];
    return sum;
}
void solve(int x1,int x2 ,int y1, int y2 ){
    if (dp[x1][x2][y1][y2] != 1e9) return;
    if(x1==x2 and y1==y2 ){
        dp[x1][x2][y1][y2]=0;
        return ;
    }
        for(int i=y1; i<y2; i++){
            solve(x1,x2,y1,i);
            solve(x1,x2,i+1,y2);
            dp[x1][x2][y1][y2]=min(dp[x1][x2][y1][y2],dp[x1][x2][y1][i]+dp[x1][x2][i+1][y2]+cnt(x1,x2,y1,y2));
        }
        for(int i=x1; i<x2; i++){
            solve(x1,i,y1,y2);
            solve(i+1,x2,y1,y2);
            dp[x1][x2][y1][y2]=min(dp[x1][x2][y1][y2],dp[x1][i][y1][y2]+dp[i+1][x2][y1][y2]+cnt(x1,x2,y1,y2));
        }
    
}
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin>>a[i][j];
        }
    }
    //x simagle 
    //y sigrdze 
    //x1 y1 
    //         x2 y2
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            pr[i][j]=pr[i-1][j]+pr[i][j-1]-pr[i-1][j-1]+a[i][j];
        }
    }
    for(int i=1; i<=50; i++){
        for(int i1=1; i1<=50; i1++){
            for(int i2=1; i2<=50; i2++){
                for(int i3=1; i3<=50; i3++){
                    dp[i][i1][i2][i3]=1e9;
                }
            }
        }
    } 
    solve(1,n,1,m);
    cout<<dp[1][n][1][m]<<endl;
}

• Subtask 1: 100 / 100