oj.uz

Submission #863375

# Submission time Handle Problem Language Result Execution time Memory
863375 2023-10-20T06:10:59 Z HuyQuang_re_Zero Raisins (IOI09_raisins) C++14
100 / 100
 179 ms 36440 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define N 55
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
using namespace std;
int sum[N][N],f[N][N][N][N],n,m,i,j;
int get(int x1,int y1,int x2,int y2)
{
    return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int cal(int x1,int y1,int x2,int y2)
{
    if(x1==x2 && y1==y2) return 0;
    if(f[x1][y1][x2][y2]>-1) return f[x1][y1][x2][y2];
    int res=round(1e9),k=get(x1,y1,x2,y2);
    for(int i=x1;i<x2;i++) res=min(res,cal(x1,y1,i,y2)+cal(i+1,y1,x2,y2)+k);
    for(int i=y1;i<y2;i++) res=min(res,cal(x1,y1,x2,i)+cal(x1,i+1,x2,y2)+k);
    return f[x1][y1][x2][y2]=res;
}
int main()
{
 //   freopen("raisins.inp","r",stdin);
   // freopen("raisins.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        {
            cin>>sum[i][j];
            sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
        }
    memset(f,-1,sizeof(f));
    cout<<cal(1,1,n,m);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 36188 KB Output is correct
2 Correct 5 ms 36188 KB Output is correct
3 Correct 5 ms 36188 KB Output is correct
4 Correct 4 ms 36188 KB Output is correct
5 Correct 4 ms 36052 KB Output is correct
6 Correct 5 ms 36188 KB Output is correct
7 Correct 5 ms 36188 KB Output is correct
8 Correct 7 ms 36188 KB Output is correct
9 Correct 9 ms 36188 KB Output is correct
10 Correct 10 ms 36188 KB Output is correct
11 Correct 9 ms 36188 KB Output is correct
12 Correct 22 ms 36288 KB Output is correct
13 Correct 33 ms 36188 KB Output is correct
14 Correct 14 ms 36440 KB Output is correct
15 Correct 38 ms 36188 KB Output is correct
16 Correct 9 ms 36188 KB Output is correct
17 Correct 20 ms 36256 KB Output is correct
18 Correct 88 ms 36188 KB Output is correct
19 Correct 140 ms 36436 KB Output is correct
20 Correct 179 ms 36280 KB Output is correct