Submission #797778

#	Time	Username	Problem	Language	Result	Execution time	Memory
797778		Liudas	Raisins (IOI09_raisins)	C++17	100 / 100	904 ms	55532 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
long long ans = 0;
vector<vector<long long>> arr(50, vector<long long> (50)), pref(55, vector<long long>(55, 0));
vector<vector<vector<vector<long long>>>> best(50, vector<vector<vector<long long>>>(50, vector<vector<long long>>(50, vector<long long>(50, 2e12))));
long long calc(int a, int b, int c, int d){
    return pref[c][d] - pref[c][b] - pref[a][d] + pref[a][b];
}
long long split(int a, int b, int c, int d){
    if(c-a==1 && d-b==1){
        return 0;
    }
    if(best[a][b][c-1][d-1] < 2e12){
        return best[a][b][c-1][d-1];
    }
    for(int i = a + 1; i < c; i ++){
        best[a][b][c-1][d-1] = min(best[a][b][c-1][d-1], split(a,b,i,d) + split(i,b,c,d) + calc(a,b,c,d));
    }
    for(int i = b + 1; i < d; i ++){
        best[a][b][c-1][d-1] = min(best[a][b][c-1][d-1], split(a,b,c,i) + split(a,i,c,d) + calc(a,b,c,d));
    }
    return best[a][b][c-1][d-1];
}
int main()
{
    int N, M;
    cin >> N >> M;
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < M; j ++){
            cin >> arr[i][j];
        }
    }
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < M; j ++){
            pref[i + 1][j + 1] = arr[i][j] + pref[i][j+1] + pref[i + 1][j] - pref[i][j];
        }
    }
    cout << split(0, 0, N, M) << endl;
    return 0;
}

• Subtask 1: 100 / 100