Submission #783195

#TimeUsernameProblemLanguageResultExecution timeMemory
783195canadavid1Raisins (IOI09_raisins)C++14
100 / 100
670 ms33636 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) begin(x),end(x) using pii = pair<int,int>; using i64 = int64_t; using i8 = int; vector<vector<int>> raisins; int Y,X; i64 memo[50*50*50*50] = {}; i64& mem(i8 sx,i8 sy,i8 ex, i8 ey) { return memo[sx*50*50*50+sy*50*50+ex*50+ey]; } i64 min_cost(i8 sx,i8 sy,i8 ex,i8 ey) { // memoize if(ey-sy <= 1 && ex - sx <= 1) { return 0; } if (mem(sx,sy,ex,ey)!=0) return mem(sx,sy,ex,ey); // rows int cost = /* count of raisins present */ 0; for(int i = sy; i < ey; i++) for(int j = sx; j < ex; j++) cost += raisins[i][j]; i64 mincost = INT64_MAX; for(int i = sx+1; i < ex;i++) { mincost = min(mincost,min_cost(sx,sy,i,ey)+min_cost(i,sy,ex,ey)); } for(int i = sy+1; i < ey;i++) { mincost = min(mincost,min_cost(sx,sy,ex,i)+min_cost(sx,i,ex,ey)); } mem(sx,sy,ex,ey) = cost + mincost; return cost + mincost; } int main() { cin >> Y >> X; raisins.assign(Y,vector<int>(X)); for(int i = 0; i < Y; i++) for(int j = 0; j < X; j++) cin >> raisins[i][j]; cout << min_cost(0,0,X,Y) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...