oj.uz

Submission #797779

# Submission time Handle Problem Language Result Execution time Memory
797779 2023-07-29T22:12:56 Z Liudas Raisins (IOI09_raisins) C++17
5 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
long long arr[50][50], pref[55][55], best[50][50][50][50];
long long calc(int a, int b, int c, int d){
    return pref[c][d] - pref[c][b] - pref[a][d] + pref[a][b];
}
long long split(int a, int b, int c, int d){
    if(c-a==1 && d-b==1){
        return 0;
    }
    if(best[a][b][c-1][d-1] < 2e12){
        return best[a][b][c-1][d-1];
    }
    for(int i = a + 1; i < c; i ++){
        best[a][b][c-1][d-1] = min(best[a][b][c-1][d-1], split(a,b,i,d) + split(i,b,c,d) + calc(a,b,c,d));
    }
    for(int i = b + 1; i < d; i ++){
        best[a][b][c-1][d-1] = min(best[a][b][c-1][d-1], split(a,b,c,i) + split(a,i,c,d) + calc(a,b,c,d));
    }
    return best[a][b][c-1][d-1];
}
int main()
{
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < M; j ++){
            cin >> arr[i][j];
        }
    }
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < M; j ++){
            pref[i + 1][j + 1] = arr[i][j] + pref[i][j+1] + pref[i + 1][j] - pref[i][j];
        }
    }
    cout << split(0, 0, N, M) << endl;
    return 0;
}

Subtask #1
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Incorrect 0 ms 212 KB Output isn't correct
6 Incorrect 0 ms 212 KB Output isn't correct
7 Incorrect 0 ms 212 KB Output isn't correct
8 Incorrect 0 ms 212 KB Output isn't correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Incorrect 1 ms 340 KB Output isn't correct
13 Incorrect 1 ms 340 KB Output isn't correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Incorrect 1 ms 340 KB Output isn't correct
16 Incorrect 0 ms 340 KB Output isn't correct
17 Incorrect 0 ms 340 KB Output isn't correct
18 Incorrect 1 ms 340 KB Output isn't correct
19 Incorrect 1 ms 340 KB Output isn't correct
20 Incorrect 1 ms 340 KB Output isn't correct