Submission #237606

#	Time	Username	Problem	Language	Result	Execution time	Memory
237606		ant101	Raisins (IOI09_raisins)	C++14	100 / 100	482 ms	53496 KiB

raisins

#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 / 100