oj.uz

Submission #867596

# Submission time Handle Problem Language Result Execution time Memory
867596 2023-10-28T20:34:45 Z Bula Raisins (IOI09_raisins) C++17
100 / 100
 185 ms 35416 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;
    }
   	if(dp[a][b][A][B] != INT_MAX) return dp[a][b][A][B];
    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:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

Subtask #1
100.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 35416 KB Output is correct
5 Correct 6 ms 35160 KB Output is correct
6 Correct 6 ms 35164 KB Output is correct
7 Correct 7 ms 35164 KB Output is correct
8 Correct 9 ms 35164 KB Output is correct
9 Correct 10 ms 35164 KB Output is correct
10 Correct 12 ms 35164 KB Output is correct
11 Correct 11 ms 35364 KB Output is correct
12 Correct 26 ms 35164 KB Output is correct
13 Correct 40 ms 35360 KB Output is correct
14 Correct 14 ms 35164 KB Output is correct
15 Correct 43 ms 35300 KB Output is correct
16 Correct 9 ms 35164 KB Output is correct
17 Correct 20 ms 35372 KB Output is correct
18 Correct 98 ms 35164 KB Output is correct
19 Correct 185 ms 35408 KB Output is correct
20 Correct 185 ms 35308 KB Output is correct