oj.uz

Submission #1020301

# Submission time Handle Problem Language Result Execution time Memory
1020301 2024-07-11T20:13:02 Z AliHasanli Raisins (IOI09_raisins) C++17
100 / 100
 517 ms 33816 KB 
#include<bits/stdc++.h>
using namespace std;
long long arr[50][50],dp[50][50][50][50],pre[50][50];
void com()
{
    pre[0][0]=arr[0][0];
    for(int j=1;j<50;j++)
        pre[0][j]=pre[0][j-1]+arr[0][j];
    for(int i=1;i<50;i++)
        for(int j=0;j<50;j++)
        {
            if(j==0)
                pre[i][j]=pre[i-1][j]+arr[i][j];
            else
                pre[i][j]=pre[i-1][j]-pre[i-1][j-1]+pre[i][j-1]+arr[i][j];
        }
}
long long sum(int x1,int y1,int x2,int y2)
{
    if(x1==0 && y1==0)
        return pre[x2][y2];
    else if(x1==0)
        return pre[x2][y2]-pre[x2][y1-1];
    else if(y1==0)
        return pre[x2][y2]-pre[x1-1][y2];
    return pre[x2][y2]-pre[x1-1][y2]-pre[x2][y1-1]+pre[x1-1][y1-1];
}
long long f(int x1,int y1,int x2,int y2)
{
    long long ans=1000000000000000000;
    if(dp[x1][y1][x2][y2])return dp[x1][y1][x2][y2];
    if(x1==x2 && y1==y2)return dp[x1][y1][x2][y2]=0;
    for(int i=x1;i<x2;i++)
        ans=min(ans,sum(x1,y1,x2,y2)+f(x1,y1,i,y2)+f(i+1,y1,x2,y2));
    for(int j=y1;j<y2;j++)
        ans=min(ans,sum(x1,y1,x2,y2)+f(x1,y1,x2,j)+f(x1,j+1,x2,y2));
    return dp[x1][y1][x2][y2]=ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    cin>>arr[i][j];
    com();
    cout<<f(0,0,n-1,m-1);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1112 KB Output is correct
8 Correct 7 ms 3420 KB Output is correct
9 Correct 16 ms 4956 KB Output is correct
10 Correct 18 ms 5980 KB Output is correct
11 Correct 21 ms 4864 KB Output is correct
12 Correct 64 ms 10580 KB Output is correct
13 Correct 88 ms 13584 KB Output is correct
14 Correct 25 ms 6212 KB Output is correct
15 Correct 132 ms 15252 KB Output is correct
16 Correct 10 ms 5208 KB Output is correct
17 Correct 45 ms 10940 KB Output is correct
18 Correct 274 ms 25428 KB Output is correct
19 Correct 454 ms 31196 KB Output is correct
20 Correct 517 ms 33816 KB Output is correct