Submission #782890

#TimeUsernameProblemLanguageResultExecution timeMemory
782890canadavid1Raisins (IOI09_raisins)C++14
85 / 100
5085 ms33532 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; map<tuple<i8,i8,i8,i8>,i64> memo; i64 min_cost(i8 sx,i8 sy,i8 ex,i8 ey) { // memoize if(ey-sy <= 1 && ex - sx <= 1) { return 0; } if (memo.count({sx,sy,ex,ey})) return memo[{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)); } memo[{sx,sy,ex,ey}] = cost + mincost; return cost + mincost; } int main() { int N,M; cin >> N >> M; raisins.assign(N,vector<int>(M)); for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) cin >> raisins[i][j]; cout << min_cost(0,0,M,N) << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...