# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
797777 | Liudas | Raisins (IOI09_raisins) | C++17 | 917 ms | 55432 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |