oj.uz

Submission #839045

# Submission time Handle Problem Language Result Execution time Memory
839045 2023-08-28T14:32:10 Z VMaksimoski008 Raisins (IOI09_raisins) C++14
15 / 100
 5000 ms 57580 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int n, m;
int mat[52][52];
ll prefix[52][52];
ll dp[52][52][52][52];

ll query(int x1, int y1, int x2, int y2) {
    ll ans = 0;

    ans += prefix[x2][y2];
    ans -= prefix[x1-1][y2];
    ans -= prefix[x2][y1-1];
    ans += prefix[x1-1][y1-1];

    return ans;
}

ll f(int x1, int y1, int x2, int y2) {
    if(x1 == x2 && y1 == y2) return 0;
    if(dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
    //cout << "(" <<  x1 << " " << y1 << "), (" << x2 << " " << y2 << ")\n";

    ll ans = 1e18;

    //make horizontal cut
    for(int i=x1; i<x2; i++) {
        ans = min(ans, f(x1, y1, i, y2) + f(i+1, y1, x2, y2));
    }
    
    //make vertical cut
    for(int i=y1; i<y2; i++) {
        ans = min(ans, f(x1, y1, x2, i) + f(x1, i+1, x2, y2));
    }

    return dp[x1][y1][x2][y1] = ans + query(x1, y1, x2, y2); 
}

int32_t main() {
    setIO();

    cin >> n >> m;
    memset(prefix, 0, sizeof(prefix));
    memset(dp, -1, sizeof(dp));

    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin >> mat[i][j];

    //build prefix table
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            prefix[i][j] += mat[i][j];
            prefix[i][j] += prefix[i-1][j];
            prefix[i][j] += prefix[i][j-1];
            prefix[i][j] -= prefix[i-1][j-1];
        }
    }

    cout << f(1, 1, n, m) << '\n';
    return 0;
}

Subtask #1
15.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 57556 KB Output is correct
2 Correct 19 ms 57484 KB Output is correct
3 Incorrect 19 ms 57572 KB Output isn't correct
4 Correct 19 ms 57448 KB Output is correct
5 Incorrect 37 ms 57556 KB Output isn't correct
6 Execution timed out 5079 ms 57476 KB Time limit exceeded
7 Execution timed out 5055 ms 57548 KB Time limit exceeded
8 Execution timed out 5080 ms 57556 KB Time limit exceeded
9 Execution timed out 5065 ms 57580 KB Time limit exceeded
10 Execution timed out 5075 ms 57568 KB Time limit exceeded
11 Execution timed out 5076 ms 57556 KB Time limit exceeded
12 Execution timed out 5083 ms 57548 KB Time limit exceeded
13 Execution timed out 5085 ms 57540 KB Time limit exceeded
14 Execution timed out 5078 ms 57516 KB Time limit exceeded
15 Execution timed out 5043 ms 57500 KB Time limit exceeded
16 Execution timed out 5066 ms 57540 KB Time limit exceeded
17 Execution timed out 5076 ms 57556 KB Time limit exceeded
18 Execution timed out 5070 ms 57488 KB Time limit exceeded
19 Execution timed out 5086 ms 57536 KB Time limit exceeded
20 Execution timed out 5065 ms 57556 KB Time limit exceeded