Submission #371251

#TimeUsernameProblemLanguageResultExecution timeMemory
371251uacoder123Raisins (IOI09_raisins)C++14
100 / 100
1418 ms58860 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define F first #define S second #define FOR(i,a,b) for (auto i = (a); i <= (b); ++i) #define NFOR(i,a,b) for(auto i = (a); i >= (b); --i) #define all(x) (x).begin(), (x).end() #define sz(x) lli(x.size()) #define mp(i,a) make_pair(i,a) #define pb(a) push_back(a) #define bit(x,b) (x&(1LL<<b)) typedef long long int lli; typedef pair <lli,lli> ii; typedef pair <ii,lli> iii; typedef vector <lli> vi; typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ii dp[50][50][50][50]; int arr[50][50],n,m; ii cal(int r1,int c1,int r2,int c2) { if(dp[r1][c1][r2][c2].F>0) return dp[r1][c1][r2][c2]; if(r1==r2&&c1==c2) { dp[r1][c1][r2][c2]=mp(0,arr[r1][c1]); return dp[r1][c1][r2][c2]; } dp[r1][c1][r2][c2]=mp(1000*25000000000000,10000000000*25000); for(int i=r1;i<r2;++i) { ii v1=cal(r1,c1,i,c2),v2=cal(i+1,c1,r2,c2); dp[r1][c1][r2][c2]=min(dp[r1][c1][r2][c2],mp(v1.F+v1.S+v2.F+v2.S,v1.S+v2.S)); } for(int i=c2-1;i>=c1;--i) { ii v1=cal(r1,c1,r2,i),v2=cal(r1,i+1,r2,c2); dp[r1][c1][r2][c2]=min(dp[r1][c1][r2][c2],mp(v1.F+v1.S+v2.F+v2.S,v1.S+v2.S)); } return dp[r1][c1][r2][c2]; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);\ cin>>n>>m; for(int i=0;i<n;++i) { for(int j=0;j<m;++j) { cin>>arr[i][j]; } } cout<<cal(0,0,n-1,m-1).F<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...