oj.uz

Submission #1020299

# Submission time Handle Problem Language Result Execution time Memory
1020299 2024-07-11T20:01:25 Z AliHasanli Raisins (IOI09_raisins) C++17
5 / 100
 548 ms 34108 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=0;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-1]+(pre[i-1][j]-pre[i-1][j-1]+pre[i][j-1]-pre[i-1][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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 0 ms 444 KB Output isn't correct
6 Incorrect 1 ms 1116 KB Output isn't correct
7 Incorrect 1 ms 1152 KB Output isn't correct
8 Incorrect 8 ms 3372 KB Output isn't correct
9 Incorrect 13 ms 4852 KB Output isn't correct
10 Incorrect 19 ms 5952 KB Output isn't correct
11 Incorrect 16 ms 4884 KB Output isn't correct
12 Incorrect 55 ms 10572 KB Output isn't correct
13 Incorrect 92 ms 13648 KB Output isn't correct
14 Incorrect 26 ms 5972 KB Output isn't correct
15 Incorrect 113 ms 15184 KB Output isn't correct
16 Incorrect 10 ms 5212 KB Output isn't correct
17 Incorrect 45 ms 11100 KB Output isn't correct
18 Incorrect 289 ms 25428 KB Output isn't correct
19 Incorrect 468 ms 31312 KB Output isn't correct
20 Incorrect 548 ms 34108 KB Output isn't correct