oj.uz

Submission #798163

# Submission time Handle Problem Language Result Execution time Memory
798163 2023-07-30T12:19:45 Z Mouad_ouj Raisins (IOI09_raisins) C++17
100 / 100
 514 ms 53324 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(ymax-ymin==0 && xmax-xmin==0)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 18 ms 53148 KB Output is correct
4 Correct 20 ms 53240 KB Output is correct
5 Correct 20 ms 53244 KB Output is correct
6 Correct 23 ms 53128 KB Output is correct
7 Correct 22 ms 53160 KB Output is correct
8 Correct 28 ms 53232 KB Output is correct
9 Correct 27 ms 53268 KB Output is correct
10 Correct 35 ms 53260 KB Output is correct
11 Correct 33 ms 53248 KB Output is correct
12 Correct 61 ms 53256 KB Output is correct
13 Correct 110 ms 53324 KB Output is correct
14 Correct 31 ms 53268 KB Output is correct
15 Correct 121 ms 53204 KB Output is correct
16 Correct 23 ms 53220 KB Output is correct
17 Correct 48 ms 53236 KB Output is correct
18 Correct 274 ms 53256 KB Output is correct
19 Correct 448 ms 53260 KB Output is correct
20 Correct 514 ms 53260 KB Output is correct