Submission #887878

#	Time	Username	Problem	Language	Result	Execution time	Memory
887878		JakobZorz	Raisins (IOI09_raisins)	C++17	100 / 100	305 ms	28756 KiB

raisins

#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
#include<cstring>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
//const int MOD=1e9+7;
//typedef pair<ll,ll>Point;
//typedef pair<ll,ll>Line;
//#define x first
//#define y second

int mat[50][50];
int sum[51][51];
int w,h;

bool dpt[51][51][51][51];
int dp[51][51][51][51];
int get(int x1,int x2,int y1,int y2){
    if(dpt[x1][x2][y1][y2])
        return dp[x1][x2][y1][y2];
    
    if(x1==x2-1&&y1==y2-1)
        return 0;
    int res=1e9;
    for(int x=x1+1;x<x2;x++)
        res=min(res,get(x1,x,y1,y2)+get(x,x2,y1,y2));
    for(int y=y1+1;y<y2;y++)
        res=min(res,get(x1,x2,y1,y)+get(x1,x2,y,y2));
    res+=sum[x2][y2]+sum[x1][y1]-sum[x2][y1]-sum[x1][y2];
    dpt[x1][x2][y1][y2]=true;
    dp[x1][x2][y1][y2]=res;
    return res;
}

void solve(){
    cin>>h>>w;
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            cin>>mat[x][y];
        }
    }
    
    for(int x=1;x<51;x++){
        for(int y=1;y<51;y++){
            sum[x][y]=mat[x-1][y-1]+sum[x-1][y]+sum[x][y-1]-sum[x-1][y-1];
        }
    }
    
    cout<<get(0,w,0,h)<<"\n";
    //cout<<get(0,1,0,2)<<"\n";
    //cout<<sum[0][0]+sum[2][2]-sum[0][2]-sum[2][0]<<"\n";
}

int main(){
    ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
    //freopen("bank.in","r",stdin);freopen("bank.out","w",stdout);
    int t=1;//cin>>t;
    while(t--)solve();
    return 0;
}

/*
 
2 3
2 7 5
1 9 5

 */

• Subtask 1: 100 / 100