oj.uz

Submission #1020300

# Submission time Handle Problem Language Result Execution time Memory
1020300 2024-07-11T20:05:51 Z AliHasanli Raisins (IOI09_raisins) C++17
10 / 100
 541 ms 33700 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][y1]-pre[x1][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
10.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 1 ms 604 KB Output isn't correct
6 Incorrect 1 ms 1116 KB Output isn't correct
7 Incorrect 1 ms 1116 KB Output isn't correct
8 Incorrect 9 ms 3536 KB Output isn't correct
9 Incorrect 13 ms 4952 KB Output isn't correct
10 Incorrect 19 ms 5980 KB Output isn't correct
11 Incorrect 16 ms 4860 KB Output isn't correct
12 Incorrect 56 ms 10520 KB Output isn't correct
13 Incorrect 92 ms 13652 KB Output isn't correct
14 Incorrect 25 ms 5976 KB Output isn't correct
15 Incorrect 137 ms 15268 KB Output isn't correct
16 Incorrect 11 ms 5440 KB Output isn't correct
17 Incorrect 46 ms 11092 KB Output isn't correct
18 Incorrect 282 ms 25424 KB Output isn't correct
19 Incorrect 481 ms 31328 KB Output isn't correct
20 Incorrect 541 ms 33700 KB Output isn't correct