oj.uz

Submission #839042

# Submission time Handle Problem Language Result Execution time Memory
839042 2023-08-28T14:26:54 Z VMaksimoski008 Raisins (IOI09_raisins) C++14
15 / 100
 5000 ms 57584 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 22 ms 57500 KB Output is correct
2 Correct 18 ms 57488 KB Output is correct
3 Incorrect 19 ms 57556 KB Output isn't correct
4 Correct 18 ms 57584 KB Output is correct
5 Incorrect 40 ms 57560 KB Output isn't correct
6 Execution timed out 5052 ms 57568 KB Time limit exceeded
7 Execution timed out 5057 ms 57544 KB Time limit exceeded
8 Execution timed out 5050 ms 57556 KB Time limit exceeded
9 Execution timed out 5073 ms 57568 KB Time limit exceeded
10 Execution timed out 5067 ms 57572 KB Time limit exceeded
11 Execution timed out 5087 ms 57548 KB Time limit exceeded
12 Execution timed out 5072 ms 57552 KB Time limit exceeded
13 Execution timed out 5078 ms 57568 KB Time limit exceeded
14 Execution timed out 5050 ms 57556 KB Time limit exceeded
15 Execution timed out 5049 ms 57548 KB Time limit exceeded
16 Execution timed out 5084 ms 57512 KB Time limit exceeded
17 Execution timed out 5067 ms 57556 KB Time limit exceeded
18 Execution timed out 5051 ms 57504 KB Time limit exceeded
19 Execution timed out 5033 ms 57556 KB Time limit exceeded
20 Execution timed out 5070 ms 57540 KB Time limit exceeded