Submission #537767

#	Time	Username	Problem	Language	Result	Execution time	Memory
537767		perchuts	Raisins (IOI09_raisins)	C++17	100 / 100	557 ms	21048 KiB

raisins

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int grid[51][51], pr[51][51], dp[51][51][51][51];

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

int solve(int x1,int y1,int x2,int y2){
    if(dp[x1][y1][x2][y2])return dp[x1][y1][x2][y2];
    if(x1==x2&&y1==y2)return dp[x1][y1][x2][y2] = 0;
    dp[x1][y1][x2][y2] = calcRect(x1,y1,x2,y2);
    int best = inf;
    for(int i=x1;i<x2;++i){
        ckmin(best,solve(x1,y1,i,y2)+solve(i+1,y1,x2,y2));
    }
    for(int i=y1;i<y2;++i){
        ckmin(best,solve(x1,y1,x2,i)+solve(x1,i+1,x2,y2));
    }
    return dp[x1][y1][x2][y2] = dp[x1][y1][x2][y2] + best;
}

int main(){_
    int n,m;cin>>n>>m;

    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            cin>>grid[i][j];    

    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] + grid[i][j];
            
    cout<<solve(1,1,n,m)<<endl;
}

• Subtask 1: 100 / 100