oj.uz

답안 #953861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
953861 2024-03-26T18:25:48 Z Ariadna 건포도 (IOI09_raisins) C++14
100 / 100
 705 ms 29528 KB 
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;
using vii = vector<vi>;
using vi3 = vector<vii>;
using vi4 = vector<vi3>;

vii r, sum;
vi4 dp;

int value(int x1, int y1, int x2, int y2) {
    return sum[x2+1][y2+1] - sum[x1][y2+1] - sum[x2+1][y1] + sum[x1][y1];
}

int raisins(int x1, int y1, int x2, int y2) {
    if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];

    if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = 0;

    dp[x1][y1][x2][y2] = 1e9;
    for (int x = x1; x < x2; ++x) {
        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], raisins(x1, y1, x, y2) + raisins(x+1, y1, x2, y2) + value(x1, y1, x2, y2));
    }
    for (int y = y1; y < y2; ++y) {
        dp[x1][y1][x2][y2] = min(dp[x1][y1][x2][y2], raisins(x1, y1, x2, y) + raisins(x1, y+1, x2, y2) + value(x1, y1, x2, y2));
    }

    return dp[x1][y1][x2][y2];
}

int main() {
    int n, m;
    cin >> n >> m;
    r = vii (n, vi(m));
    sum = vii(n+1, vi(m+1, 0));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> r[i][j];
            sum[i+1][j+1] = sum[i+1][j] + sum[i][j+1] - sum[i][j] + r[i][j];
        }
    }
    dp = vi4(n, vi3(m, vii(n, vi(m, -1))));
    cout << raisins(0, 0, n-1, m-1) << '\n';

    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 8 ms 1372 KB Output is correct
9 Correct 14 ms 2016 KB Output is correct
10 Correct 22 ms 2628 KB Output is correct
11 Correct 18 ms 2140 KB Output is correct
12 Correct 70 ms 5724 KB Output is correct
13 Correct 116 ms 8280 KB Output is correct
14 Correct 30 ms 2908 KB Output is correct
15 Correct 141 ms 9596 KB Output is correct
16 Correct 12 ms 1880 KB Output is correct
17 Correct 60 ms 4700 KB Output is correct
18 Correct 374 ms 18520 KB Output is correct
19 Correct 612 ms 26964 KB Output is correct
20 Correct 705 ms 29528 KB Output is correct