Submission #557857

#	Time	Username	Problem	Language	Result	Execution time	Memory
557857		kevinxiehk	Raisins (IOI09_raisins)	C++17	100 / 100	226 ms	15544 KiB

raisins

#include <bits/stdc++.h>
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define ick cout<<"ickbmi32.9\n"
using namespace std;
int mem[55][55][55][55];
int pre[55][55];
int arr[55][55];
int n,m;
int solve(int x1,int x2,int y1,int y2){
    if(mem[x1][x2][y1][y2]!=0)return mem[x1][x2][y1][y2];
    if(x1==x2&&y1==y2)return 0;
    int a=999999999;
    for(int i=x1;i<x2;i++)a=min(a,solve(x1,i,y1,y2)+solve(i+1,x2,y1,y2));
    for(int i=y1;i<y2;i++)a=min(a,solve(x1,x2,y1,i)+solve(x1,x2,i+1,y2));
    return mem[x1][x2][y1][y2]=a+pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>arr[i][j];
            pre[i][j]=arr[i][j]+pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1];
        }
    }
    cout<<solve(1,n,1,m)<<'\n';
    return 0;
}

• Subtask 1: 100 / 100