Submission #1217504

#TimeUsernameProblemLanguageResultExecution timeMemory
1217504jasonicRaisins (IOI09_raisins)C++20
100 / 100
188 ms60968 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fastIO cin.tie(0); ios::sync_with_stdio(false) ll dp[55][55][55][55]; // thing ll sum[55][55][55][55]; // thing ll vals[55][55]; int main() { fastIO; int n, m; cin >> n >> m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> vals[i][j]; } } for(int xsz = 1; xsz <= m; xsz++) { for(int ysz = 1; ysz <= n; ysz++) { for(int x = 0; x+xsz-1 < m; x++) { for(int y = 0; y+ysz-1 < n; y++) { if(xsz == 1 && ysz == 1) { dp[x][x][y][y] = 0; sum[x][x][y][y] = vals[y][x]; } else { int xr = x + xsz - 1; int yr = y + ysz - 1; dp[x][xr][y][yr] = LLONG_MAX; if(xsz > 1) { sum[x][xr][y][yr] = sum[x][x][y][yr] + sum[x+1][xr][y][yr]; for(int leftBound = x; leftBound < xr; leftBound++) { dp[x][xr][y][yr] = min(dp[x][xr][y][yr], dp[x][leftBound][y][yr] + dp[leftBound+1][xr][y][yr] + sum[x][xr][y][yr]); } } if(ysz > 1) { sum[x][xr][y][yr] = sum[x][xr][y][y] + sum[x][xr][y+1][yr]; for(int leftBound = y; leftBound < yr; leftBound++) { dp[x][xr][y][yr] = min(dp[x][xr][y][yr], dp[x][xr][y][leftBound] + dp[x][xr][leftBound+1][yr] + sum[x][xr][y][yr]); } } } // printf("%d %d %d %d: %d, sum was %d\n", x, x+xsz-1, y, y+ysz-1, dp[x][x+xsz-1][y][y+ysz-1], sum[x][x+xsz-1][y][y+ysz-1]); } } } } cout << dp[0][m-1][0][n-1]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...