Submission #798161

# Submission time Handle Problem Language Result Execution time Memory
798161 2023-07-30T12:18:08 Z Mouad_ouj Raisins (IOI09_raisins) C++17
5 / 100
5000 ms 53344 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)
{
    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)||(ymax-ymin==0 && xmax-xmin==0))
    return cur;
    if(memo[xmin][xmax][ymin][ymax]!=-1)
    return memo[xmin][xmax][ymin][ymax];
    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);
}
# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 53204 KB Output isn't correct
2 Correct 19 ms 53204 KB Output is correct
3 Incorrect 20 ms 53232 KB Output isn't correct
4 Incorrect 19 ms 53148 KB Output isn't correct
5 Incorrect 20 ms 53224 KB Output isn't correct
6 Incorrect 21 ms 53204 KB Output isn't correct
7 Incorrect 21 ms 53204 KB Output isn't correct
8 Incorrect 62 ms 53260 KB Output isn't correct
9 Incorrect 110 ms 53252 KB Output isn't correct
10 Incorrect 164 ms 53248 KB Output isn't correct
11 Incorrect 137 ms 53252 KB Output isn't correct
12 Incorrect 652 ms 53256 KB Output isn't correct
13 Incorrect 1233 ms 53256 KB Output isn't correct
14 Incorrect 260 ms 53248 KB Output isn't correct
15 Incorrect 1636 ms 53264 KB Output isn't correct
16 Incorrect 79 ms 53204 KB Output isn't correct
17 Incorrect 476 ms 53256 KB Output isn't correct
18 Execution timed out 5068 ms 53216 KB Time limit exceeded
19 Execution timed out 5053 ms 53344 KB Time limit exceeded
20 Execution timed out 5043 ms 53204 KB Time limit exceeded