Submission #797777

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
797777	2023-07-29T22:06:00 Z	Liudas	Raisins (IOI09_raisins)	C++17	100 / 100	917 ms	55432 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(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) + 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	73 ms	55216 KB	Output is correct
2	Correct	75 ms	55264 KB	Output is correct
3	Correct	71 ms	55224 KB	Output is correct
4	Correct	73 ms	55224 KB	Output is correct
5	Correct	75 ms	55212 KB	Output is correct
6	Correct	75 ms	55432 KB	Output is correct
7	Correct	75 ms	55236 KB	Output is correct
8	Correct	82 ms	55236 KB	Output is correct
9	Correct	88 ms	55244 KB	Output is correct
10	Correct	98 ms	55332 KB	Output is correct
11	Correct	94 ms	55332 KB	Output is correct
12	Correct	151 ms	55244 KB	Output is correct
13	Correct	205 ms	55336 KB	Output is correct
14	Correct	104 ms	55244 KB	Output is correct
15	Correct	240 ms	55332 KB	Output is correct
16	Correct	85 ms	55332 KB	Output is correct
17	Correct	145 ms	55340 KB	Output is correct
18	Correct	511 ms	55372 KB	Output is correct
19	Correct	785 ms	55288 KB	Output is correct
20	Correct	917 ms	55360 KB	Output is correct