제출 #1225286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225286		pensive	건포도 (IOI09_raisins)	C++20	100 / 100	457 ms	34616 KiB

raisins

#include <bits/stdc++.h>

using namespace std;
#define REP(a,i,n) for (int i=a;i<n;i++)
#define ll long long

ll choc[51][51], memo[51][51][51][51];

ll func(int a, int b, int x, int y) {
    if ((a==x && b==y)) {
        return 0;
    }
    else if (memo[a][b][x][y]>0) {
        return memo[a][b][x][y];
    }
    ll mini = 1e18, cur = choc[x][y] + choc[a-1][b-1] - choc[a-1][y] - choc[x][b-1];
    //cout << a << ' ' << b << ' ' << x << ' ' << y << ": " <<cur << endl;
    REP(a, i, x) {
        mini = min(mini, func(a, b, i, y) + func(i+1, b, x, y));
    }
    REP(b, j, y) {
        mini = min(mini, func(a, b, x, j) + func(a, j+1, x, y));
    }
    memo[a][b][x][y] = mini+cur;
    return memo[a][b][x][y];
}

void prefixing(int n, int m) {
    REP(1, i, n+1) {
        REP(1, j, m+1) {
            choc[i][j]+= choc[i][j-1];
        }
    }
    REP(1, j, m+1) {
        REP(1, i, n+1) {
            choc[i][j]+= choc[i-1][j];
        }
    }
}

int main() {
    int n, m; cin >> n >> m;
    REP(1, i, n+1) {
        REP(1, j, m+1) {
            cin >> choc[i][j];
        }
    }
    prefixing(n, m);
    cout << func(1, 1, n, m);
    return 0;
}

• Subtask 1: 100 / 100