oj.uz

답안 #797777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797777 2023-07-29T22:06:00 Z Liudas 건포도 (IOI09_raisins) C++17
100 / 100
 917 ms 55432 KB 
#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
vector<vector<long long>> arr(50, vector<long long> (50)), pref(55, vector<long long>(55, 0));
vector<vector<vector<vector<long long>>>> best(50, vector<vector<vector<long long>>>(50, vector<vector<long long>>(50, vector<long long>(50, 2e12))));
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(best[a][b][c-1][d-1] < 2e12){
        return best[a][b][c-1][d-1];
    }
    if(c-a==1 && d-b==1){
        best[a][b][c-1][d-1] = 0;
        return 0;
    }
    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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 55216 KB Output is correct
2 Correct 75 ms 55264 KB Output is correct
3 Correct 71 ms 55224 KB Output is correct
4 Correct 73 ms 55224 KB Output is correct
5 Correct 75 ms 55212 KB Output is correct
6 Correct 75 ms 55432 KB Output is correct
7 Correct 75 ms 55236 KB Output is correct
8 Correct 82 ms 55236 KB Output is correct
9 Correct 88 ms 55244 KB Output is correct
10 Correct 98 ms 55332 KB Output is correct
11 Correct 94 ms 55332 KB Output is correct
12 Correct 151 ms 55244 KB Output is correct
13 Correct 205 ms 55336 KB Output is correct
14 Correct 104 ms 55244 KB Output is correct
15 Correct 240 ms 55332 KB Output is correct
16 Correct 85 ms 55332 KB Output is correct
17 Correct 145 ms 55340 KB Output is correct
18 Correct 511 ms 55372 KB Output is correct
19 Correct 785 ms 55288 KB Output is correct
20 Correct 917 ms 55360 KB Output is correct