oj.uz

Submission #537767

# Submission time Handle Problem Language Result Execution time Memory
537767 2022-03-15T13:31:01 Z perchuts Raisins (IOI09_raisins) C++17
100 / 100
 557 ms 21048 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 1 ms 968 KB Output is correct
8 Correct 8 ms 2632 KB Output is correct
9 Correct 14 ms 3656 KB Output is correct
10 Correct 20 ms 4300 KB Output is correct
11 Correct 17 ms 3796 KB Output is correct
12 Correct 57 ms 7436 KB Output is correct
13 Correct 108 ms 9380 KB Output is correct
14 Correct 34 ms 4668 KB Output is correct
15 Correct 121 ms 10316 KB Output is correct
16 Correct 12 ms 3656 KB Output is correct
17 Correct 49 ms 7372 KB Output is correct
18 Correct 292 ms 15968 KB Output is correct
19 Correct 478 ms 19516 KB Output is correct
20 Correct 557 ms 21048 KB Output is correct