oj.uz

Submission #771872

# Submission time Handle Problem Language Result Execution time Memory
771872 2023-07-03T10:51:34 Z cnastea Raisins (IOI09_raisins) C++14
30 / 100
 829 ms 54360 KB 
#include <bits/stdc++.h>
using namespace std;
int a[50][50];
int d[50][50][50][50];
bool b[50][50][50][50];

int f(int p, int q, int r, int s){
    if(p == r && q == s) {
        return 0;
    }
    if (b[p][q][r][s]) {
        return d[p][q][r][s];
    }
    else b[p][q][r][s] = 1;
    int m = 1e9, t = 0;
    for(int i = p; i <= r; i++){
        for(int j = q; j <= s; j++){
            t += a[i][j];
        }
    }
    for(int i = p; i <= r; i++){
        int x, y;
        x = f(p, q, i-1, s);
        y = f(i, q, r, s);
        m = min(m, x + y + t);
    }
    for(int i = q; i <= s; i++){
        int x, y;
        x = f(p, q, r, i-1);
        y = f(p, i, r, s);
        m = min(m, x + y + t);
    }
    d[p][q][r][s] = m;
    return m;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    cout << f(0, 0, n-1, m-1);
    return 0;
}

Subtask #1
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 432 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Incorrect 1 ms 1076 KB Output isn't correct
7 Correct 1 ms 1236 KB Output is correct
8 Runtime error 17 ms 7556 KB Execution killed with signal 6
9 Runtime error 26 ms 10188 KB Execution killed with signal 6
10 Runtime error 36 ms 11984 KB Execution killed with signal 6
11 Runtime error 35 ms 10808 KB Execution killed with signal 11
12 Runtime error 95 ms 20080 KB Execution killed with signal 11
13 Runtime error 150 ms 25252 KB Execution killed with signal 11
14 Runtime error 46 ms 13020 KB Execution killed with signal 11
15 Runtime error 186 ms 27748 KB Execution killed with signal 11
16 Incorrect 15 ms 4820 KB Output isn't correct
17 Runtime error 77 ms 19152 KB Execution killed with signal 6
18 Runtime error 436 ms 41932 KB Execution killed with signal 11
19 Runtime error 718 ms 51088 KB Execution killed with signal 11
20 Runtime error 829 ms 54360 KB Execution killed with signal 11