oj.uz

Submission #237606

# Submission time Handle Problem Language Result Execution time Memory
237606 2020-06-07T17:40:14 Z ant101 Raisins (IOI09_raisins) C++14
100 / 100
 482 ms 53496 KB 
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
using namespace std;

//#define RDEBUG 1
#ifdef RDEBUG
#define D(x) x
#else
#define D(x)
#endif
#define inf 0x7fffffff
#define MOD 1000000007

typedef long long ll;


ll add(ll a, ll b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
ll sub(ll a, ll b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

ll mul(ll a, ll b) {
    return (a * b)%MOD;
}

void add_self(ll& a, ll b) {
    a = add(a, b);
}
void sub_self(ll& a, ll b) {
    a = sub(a, b);
}
void mul_self(ll& a, ll b) {
    a = mul(a, b);
}


const ll MAXN = 51;

ll pref[MAXN][MAXN];
ll grid[MAXN][MAXN];
ll dp[MAXN][MAXN][MAXN][MAXN];
ll N, M;

ll f(ll x1, ll y1, ll x2, ll y2) {
    if (x1 == x2 && y1 == y2) {
        return 0;
    }
    if (dp[x1][y1][x2][y2] != -1) {
        return dp[x1][y1][x2][y2];
    }
    ll curr = 1e13;
    for (ll i = x1; i<x2; i++) {
        curr = min(curr, f(x1, y1, i, y2)+f(i+1, y1, x2, y2));
    }
    for (ll i = y1; i<y2; i++) {
        curr = min(curr, f(x1, y1, x2, i)+f(x1, i+1, x2, y2));
    }
    curr+=pref[x2][y2]-pref[x2][y1-1]-pref[x1-1][y2]+pref[x1-1][y1-1];
    dp[x1][y1][x2][y2] = curr;
    return curr;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    for (ll i = 1; i<=N; i++) {
        for (ll j = 1; j <= M; j++) {
            cin >> grid[i][j];
        }
    }
    memset(dp, -1, sizeof(dp));
    for (ll i = 1; i<=N; i++) {
        for (ll j = 1; j<=M; j++) {
            pref[i][j]+=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+grid[i][j];
        }
    }
    cout << f(1, 1, N, M) << "\n";
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 53376 KB Output is correct
2 Correct 31 ms 53240 KB Output is correct
3 Correct 32 ms 53248 KB Output is correct
4 Correct 31 ms 53376 KB Output is correct
5 Correct 33 ms 53248 KB Output is correct
6 Correct 32 ms 53240 KB Output is correct
7 Correct 32 ms 53240 KB Output is correct
8 Correct 37 ms 53368 KB Output is correct
9 Correct 40 ms 53376 KB Output is correct
10 Correct 46 ms 53240 KB Output is correct
11 Correct 50 ms 53368 KB Output is correct
12 Correct 71 ms 53368 KB Output is correct
13 Correct 99 ms 53368 KB Output is correct
14 Correct 50 ms 53376 KB Output is correct
15 Correct 122 ms 53368 KB Output is correct
16 Correct 39 ms 53368 KB Output is correct
17 Correct 63 ms 53376 KB Output is correct
18 Correct 251 ms 53496 KB Output is correct
19 Correct 408 ms 53376 KB Output is correct
20 Correct 482 ms 53368 KB Output is correct