Submission #797778

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797778	2023-07-29T22:07:36 Z	Liudas	Raisins (IOI09_raisins)	C++17	100 / 100	904 ms	55532 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	70 ms	55312 KB	Output is correct
2	Correct	70 ms	55280 KB	Output is correct
3	Correct	74 ms	55532 KB	Output is correct
4	Correct	69 ms	55244 KB	Output is correct
5	Correct	69 ms	55300 KB	Output is correct
6	Correct	76 ms	55208 KB	Output is correct
7	Correct	70 ms	55304 KB	Output is correct
8	Correct	78 ms	55328 KB	Output is correct
9	Correct	87 ms	55244 KB	Output is correct
10	Correct	95 ms	55244 KB	Output is correct
11	Correct	89 ms	55272 KB	Output is correct
12	Correct	146 ms	55256 KB	Output is correct
13	Correct	200 ms	55332 KB	Output is correct
14	Correct	109 ms	55336 KB	Output is correct
15	Correct	233 ms	55336 KB	Output is correct
16	Correct	85 ms	55256 KB	Output is correct
17	Correct	135 ms	55332 KB	Output is correct
18	Correct	499 ms	55440 KB	Output is correct
19	Correct	796 ms	55336 KB	Output is correct
20	Correct	904 ms	55372 KB	Output is correct