oj.uz

Submission #867595

# Submission time Handle Problem Language Result Execution time Memory
867595 2023-10-28T20:21:00 Z Bula Raisins (IOI09_raisins) C++17
25 / 100
 5000 ms 35420 KB 
#include <bits/stdc++.h>
using namespace std;
int n, m, x[55][55], dp[55][55][55][55], pref[55][55];

int rec(int a, int b, int A, int B){
    if(a == A && b == B){
        return 0;
    }
    int sum = pref[A][B] + pref[a - 1][b - 1] - pref[a - 1][B] - pref[A][b - 1];
    for(int i = a; i < A; i++){
        dp[a][b][A][B] = min(dp[a][b][A][B], sum + rec(a, b, i, B) + rec(i + 1, b, A, B));
    }
    for(int i = b; i < B; i++){
        dp[a][b][A][B] = min(dp[a][b][A][B], sum + rec(a, b, A, i) + rec(a, i + 1, A, B));
    }
    return dp[a][b][A][B];
}


main(){
    ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= 50; i++){
        for(int j = 1; j <= 50; j++){
            for(int k = 1; k <= 50; k++){
                for(int l = 1; l <= 50; l++){
                    dp[i][j][k][l] = INT_MAX;
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> x[i][j];
            dp[i][j][i][j] = 0; 
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            pref[i][j] = x[i][j] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
        }
    }

    cout << rec(1, 1, n, m) << endl;
}

Compilation message

raisins.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main(){
      | ^~~~

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35160 KB Output is correct
2 Correct 6 ms 35164 KB Output is correct
3 Correct 6 ms 35164 KB Output is correct
4 Correct 6 ms 35164 KB Output is correct
5 Correct 45 ms 35164 KB Output is correct
6 Execution timed out 5073 ms 35164 KB Time limit exceeded
7 Execution timed out 5030 ms 35160 KB Time limit exceeded
8 Execution timed out 5059 ms 35164 KB Time limit exceeded
9 Execution timed out 5034 ms 35160 KB Time limit exceeded
10 Execution timed out 5055 ms 35164 KB Time limit exceeded
11 Execution timed out 5040 ms 35420 KB Time limit exceeded
12 Execution timed out 5053 ms 35164 KB Time limit exceeded
13 Execution timed out 5027 ms 35164 KB Time limit exceeded
14 Execution timed out 5094 ms 35160 KB Time limit exceeded
15 Execution timed out 5053 ms 35164 KB Time limit exceeded
16 Execution timed out 5067 ms 35164 KB Time limit exceeded
17 Execution timed out 5097 ms 35160 KB Time limit exceeded
18 Execution timed out 5041 ms 35160 KB Time limit exceeded
19 Execution timed out 5022 ms 35160 KB Time limit exceeded
20 Execution timed out 5050 ms 35164 KB Time limit exceeded