oj.uz

Submission #239173

# Submission time Handle Problem Language Result Execution time Memory
239173 2020-06-14T16:53:49 Z DavidDamian Raisins (IOI09_raisins) C++11
25 / 100
 5000 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
int n,m;
int A[55][55];
int sum[55][55];
int getSum(int i,int j,int a,int b)
{
    int total=sum[j][b]-sum[j][a-1]-sum[i-1][b]+sum[i-1][a-1];
    return total;
}
int DivideConquer(int i,int j,int a,int b)
{
    if(i==j && a==b)
        return 0;
    int minimum=INT_MAX;
    for(int i_nxt=i;i_nxt<j;i_nxt++){
        minimum=min(minimum,DivideConquer(i,i_nxt,a,b)
                    +DivideConquer(i_nxt+1,j,a,b)
                    +getSum(i,j,a,b));
    }
    for(int a_nxt=a;a_nxt<b;a_nxt++){
        minimum=min(minimum,DivideConquer(i,j,a,a_nxt)
                    +DivideConquer(i,j,a_nxt+1,b)
                    +getSum(i,j,a,b));
    }
    return minimum;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>A[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j];
        }
    }
    int total=DivideConquer(1,n,1,m);
    cout<<total<<'\n';
    return 0;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 46 ms 384 KB Output is correct
6 Execution timed out 5040 ms 256 KB Time limit exceeded
7 Execution timed out 5060 ms 384 KB Time limit exceeded
8 Execution timed out 5061 ms 384 KB Time limit exceeded
9 Execution timed out 5055 ms 384 KB Time limit exceeded
10 Execution timed out 5061 ms 384 KB Time limit exceeded
11 Execution timed out 5047 ms 256 KB Time limit exceeded
12 Execution timed out 5039 ms 512 KB Time limit exceeded
13 Execution timed out 5048 ms 384 KB Time limit exceeded
14 Execution timed out 5054 ms 384 KB Time limit exceeded
15 Execution timed out 5059 ms 384 KB Time limit exceeded
16 Execution timed out 5061 ms 384 KB Time limit exceeded
17 Execution timed out 5049 ms 384 KB Time limit exceeded
18 Execution timed out 5067 ms 384 KB Time limit exceeded
19 Execution timed out 5065 ms 384 KB Time limit exceeded
20 Execution timed out 5096 ms 384 KB Time limit exceeded