Submission #797776

#	Time	Username	Problem	Language	Result	Execution time	Memory
797776		Liudas	Raisins (IOI09_raisins)	C++17	100 / 100	942 ms	55380 KiB

raisins

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

• Subtask 1: 100 / 100