oj.uz

Submission #236225

# Submission time Handle Problem Language Result Execution time Memory
236225 2020-05-31T18:02:57 Z nicolaalexandra Raisins (IOI09_raisins) C++14
25 / 100
 5000 ms 384 KB 
#include <bits/stdc++.h>
#define DIM 60
#define INF 2000000000
using namespace std;

int sp[DIM][DIM],a[DIM][DIM];
int n,m,i,j;
int solve (int x, int y, int x2, int y2){
    if (x == x2 && y == y2)
        return 0;

    int sol = INF;

    for (int i=y;i<y2;i++)
        sol = min (sol,solve(x,y,x2,i) + solve(x,i+1,x2,y2));

    for (int i=x;i<x2;i++)
        sol = min (sol,solve(x,y,i,y2) + solve(i+1,y,x2,y2));

    return sol + sp[x2][y2] - sp[x2][y-1] - sp[x-1][y2] + sp[x-1][y-1];

}
int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            cin>>a[i][j];
            sp[i][j] = sp[i-1][j] + sp[i][j-1] - sp[i-1][j-1] + a[i][j];
        }

    cout<<solve (1,1,n,m);


    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 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 45 ms 384 KB Output is correct
6 Execution timed out 5044 ms 256 KB Time limit exceeded
7 Execution timed out 5066 ms 384 KB Time limit exceeded
8 Execution timed out 5062 ms 384 KB Time limit exceeded
9 Execution timed out 5054 ms 384 KB Time limit exceeded
10 Execution timed out 5059 ms 384 KB Time limit exceeded
11 Execution timed out 5070 ms 384 KB Time limit exceeded
12 Execution timed out 5075 ms 256 KB Time limit exceeded
13 Execution timed out 5061 ms 384 KB Time limit exceeded
14 Execution timed out 5026 ms 384 KB Time limit exceeded
15 Execution timed out 5071 ms 384 KB Time limit exceeded
16 Execution timed out 5066 ms 384 KB Time limit exceeded
17 Execution timed out 5070 ms 384 KB Time limit exceeded
18 Execution timed out 5071 ms 384 KB Time limit exceeded
19 Execution timed out 5078 ms 384 KB Time limit exceeded
20 Execution timed out 5069 ms 384 KB Time limit exceeded