oj.uz

Submission #1083106

# Submission time Handle Problem Language Result Execution time Memory
1083106 2024-09-02T14:59:42 Z toast12 Raisins (IOI09_raisins) C++14
25 / 100
 5000 ms 440 KB 
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> ps;

// minimum cost to cut a piece of chocolate completely with corners at (i, j) and (k, l)
int cut(int i, int j, int k, int l) {
    if (i == k && j == l)
        return 0;
    int x = ps[k][l]-ps[k][j-1]-ps[i-1][l]+ps[i-1][j-1];
    int ans = INT_MAX;
    // only one row left
    if (i == k) {
        // only two columns left
        if (j+1 == l)
            return x;
        for (int col = j; col < l; col++) {
            ans = min(ans, x+cut(i, j, k, col)+cut(i, col+1, k, l));
        }
    }
    // only one column left
    else if (j == l) {
        // only two rows left
        if (i+1 == k)
            return x;
        for (int row = i; row < k; row++) {
            ans = min(ans, x+cut(i, j, row, l)+cut(row+1, j, k, l));
        }
    }
    else {
        // iterate over all horizontal cuts
        for (int h = i; h < k; h++) {
            ans = min(ans, x+cut(i, j, h, l)+cut(h+1, j, k, l));
        }
        // iterate over all vertical cuts
        for (int v = j; v < l; v++) {
            ans = min(ans, x+cut(i, j, k, v)+cut(i, v+1, k, l));
        }
    }
    if (ans == INT_MAX)
        ans = x;
    return ans;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n+1, vector<int>(m+1));
    ps.resize(n+1, vector<int>(m+1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ps[i][j] += ps[i][j-1]+grid[i][j];
        }
        for (int j = 1; j <= m; j++) {
            ps[i][j] += ps[i-1][j];
        }
    }
    cout << cut(1, 1, n, m) << '\n';
    return 0;
}

Subtask #1
25.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 16 ms 440 KB Output is correct
6 Execution timed out 5031 ms 344 KB Time limit exceeded
7 Execution timed out 5068 ms 348 KB Time limit exceeded
8 Execution timed out 5043 ms 344 KB Time limit exceeded
9 Execution timed out 5051 ms 344 KB Time limit exceeded
10 Execution timed out 5044 ms 344 KB Time limit exceeded
11 Execution timed out 5045 ms 348 KB Time limit exceeded
12 Execution timed out 5057 ms 348 KB Time limit exceeded
13 Execution timed out 5053 ms 352 KB Time limit exceeded
14 Execution timed out 5029 ms 344 KB Time limit exceeded
15 Execution timed out 5043 ms 436 KB Time limit exceeded
16 Execution timed out 5017 ms 344 KB Time limit exceeded
17 Execution timed out 5048 ms 344 KB Time limit exceeded
18 Execution timed out 5028 ms 348 KB Time limit exceeded
19 Execution timed out 5099 ms 344 KB Time limit exceeded
20 Execution timed out 5071 ms 348 KB Time limit exceeded