Submission #957686

#	Time	Username	Problem	Language	Result	Execution time	Memory
957686		hirayuu_oj	Raisins (IOI09_raisins)	C++17	100 / 100	134 ms	53588 KiB

raisins

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,a,b) for(int i=a; i<(b); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=1LL<<60;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> r(n+1,vector<ll>(m+1,0));
    rep(i,n){
        rep(j,m){
            cin>>r[i+1][j+1];
            r[i+1][j+1]+=r[i][j+1]+r[i+1][j]-r[i][j];
        }
    }
    ll dp[51][51][51][51];
    rep2(i,1,n+1){
        rep(j,n){
            ll lf=j,ri=j+i;
            if(ri>n)break;
            rep2(k,1,m+1){
                rep(l,m){
                    ll up=l,dn=l+k;
                    if(dn>m)break;
                    dp[lf][ri][up][dn]=INF;
                    ll raisin=r[ri][dn]+r[lf][up]-r[lf][dn]-r[ri][up];
                    if(i==1 and k==1){
                        dp[lf][ri][up][dn]=0;
                        continue;
                    }
                    rep2(c,lf+1,ri){
                        dp[lf][ri][up][dn]=min(dp[lf][ri][up][dn],raisin+dp[lf][c][up][dn]+dp[c][ri][up][dn]);
                    }
                    rep2(c,up+1,dn){
                        dp[lf][ri][up][dn]=min(dp[lf][ri][up][dn],raisin+dp[lf][ri][up][c]+dp[lf][ri][c][dn]);
                    }
                }
            }
        }
    }
    cout<<dp[0][n][0][m]<<"\n";
}

• Subtask 1: 100 / 100