oj.uz

답안 #337478

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
337478 2020-12-21T02:03:52 Z arbor 건포도 (IOI09_raisins) C++17
30 / 100
 1010 ms 22880 KB 
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 55;
int N, M, ps[MN][MN], dp[MN][MN][MN][MN];

int go(int x1, int y1, int x2, int y2) {
    if (dp[x1][y1][x2][y2]) return dp[x1][y1][x2][y2];
    if (x1 == x2 && y1 == y2) return 0;
    int ret = 1e9;
    for (int nx = x1 + 1; nx <= x2; nx++)
        ret = min(ret, go(x1, y1, nx - 1, y2) + go(nx, y1, x2, y2));
    for (int ny = y1 + 1; ny <= y2; ny++)
        ret = min(ret, go(x1, y1, x2, ny - 1) + go(x1, ny, x2, y2));
    ret += ps[x2][y2] - ps[x2][y1 - 1] - ps[x1 - 1][y1] + ps[x1 - 1][y1 - 1];
    return dp[x1][y1][x2][y2] = ret;
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= M; j++)
            cin >> ps[i][j], ps[i][j] += ps[i - 1][j] + ps[i][j - 1] - ps[i - 1][j - 1];
    cout << go(1, 1, N, M) << '\n';
    return 0;
}

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Incorrect 1 ms 620 KB Output isn't correct
6 Correct 1 ms 876 KB Output is correct
7 Incorrect 2 ms 1004 KB Output isn't correct
8 Incorrect 13 ms 2796 KB Output isn't correct
9 Incorrect 26 ms 3820 KB Output isn't correct
10 Incorrect 32 ms 4716 KB Output isn't correct
11 Incorrect 28 ms 3948 KB Output isn't correct
12 Incorrect 98 ms 7788 KB Output isn't correct
13 Incorrect 168 ms 9836 KB Output isn't correct
14 Incorrect 43 ms 4844 KB Output isn't correct
15 Correct 206 ms 10988 KB Output is correct
16 Incorrect 20 ms 3820 KB Output isn't correct
17 Incorrect 85 ms 7788 KB Output isn't correct
18 Incorrect 543 ms 17388 KB Output isn't correct
19 Correct 866 ms 21228 KB Output is correct
20 Incorrect 1010 ms 22880 KB Output isn't correct