oj.uz

Submission #798155

# Submission time Handle Problem Language Result Execution time Memory
798155 2023-07-30T12:11:24 Z YassirSalama Raisins (IOI09_raisins) C++14
100 / 100
 413 ms 53276 KB 
#include<bits/stdc++.h>
#define int long long 
using namespace std;
int tab[51][51];
int memo[51][51][51][51];
int solve(int xmin,int xmax,int ymin,int ymax)
{
  	if(xmin==xmax&&ymin==ymax) return 0;
    if(memo[xmin][xmax][ymin][ymax]!=-1)
    return memo[xmin][xmax][ymin][ymax];
    int ans=10000000000000000,cur=0;
    for(int x=xmin;x<=xmax;x++)
    {
        for(int y=ymin;y<=ymax;y++)
            cur+=tab[x][y];
    }
    if((xmax-xmin==1 && ymax-ymin==0)||(xmax-xmin==0 && ymax-ymin==1))
    return cur;
    for(int x=xmin+1;x<=xmax;x++)
        ans=min(ans,solve(xmin,x-1,ymin,ymax)+solve(x,xmax,ymin,ymax)+cur);
    for(int y=ymin+1;y<=ymax;y++)
        ans=min(ans,solve(xmin,xmax,ymin,y-1)+solve(xmin,xmax,y,ymax)+cur);
    memo[xmin][xmax][ymin][ymax]=ans;
    return ans;
}
signed main()
{
    memset(memo,-1,sizeof(memo));
    int n,m;
    cin>>n>>m;
    for(int x=0;x<n;x++)
    {
        for(int y=0;y<m;y++)
            cin>>tab[x][y];
    }
    cout<<solve(0,n-1,0,m-1);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 53204 KB Output is correct
2 Correct 19 ms 53204 KB Output is correct
3 Correct 22 ms 53252 KB Output is correct
4 Correct 19 ms 53204 KB Output is correct
5 Correct 19 ms 53224 KB Output is correct
6 Correct 19 ms 53252 KB Output is correct
7 Correct 20 ms 53196 KB Output is correct
8 Correct 22 ms 53204 KB Output is correct
9 Correct 26 ms 53204 KB Output is correct
10 Correct 32 ms 53208 KB Output is correct
11 Correct 28 ms 53256 KB Output is correct
12 Correct 53 ms 53268 KB Output is correct
13 Correct 74 ms 53256 KB Output is correct
14 Correct 33 ms 53204 KB Output is correct
15 Correct 88 ms 53260 KB Output is correct
16 Correct 24 ms 53252 KB Output is correct
17 Correct 44 ms 53176 KB Output is correct
18 Correct 219 ms 53268 KB Output is correct
19 Correct 344 ms 53264 KB Output is correct
20 Correct 413 ms 53276 KB Output is correct