제출 #1220443

#제출 시각아이디문제언어결과실행 시간메모리
1220443AlgorithmWarriorRaisins (IOI09_raisins)C++20
100 / 100
247 ms21952 KiB
#include <bits/stdc++.h> #define MAX 53 using namespace std; int sp[MAX][MAX]; int dp[MAX][MAX][MAX][MAX]; int N,M; void read() { cin>>N>>M; int i,j; for(i=1;i<=N;++i) for(j=1;j<=M;++j) cin>>sp[i][j]; } void precalc() { int i,j; for(i=1;i<=N;++i) for(j=1;j<=M;++j) sp[i][j]+=sp[i-1][j]+sp[i][j-1]-sp[i-1][j-1]; } int dpr(int l1,int c1,int l2,int c2) { if(l1==l2 && c1==c2) return 0; if(dp[l1][c1][l2][c2]) return dp[l1][c1][l2][c2]; int i; dp[l1][c1][l2][c2]=1e9; for(i=l1;i<l2;++i) dp[l1][c1][l2][c2]=min(dp[l1][c1][l2][c2],dpr(l1,c1,i,c2)+dpr(i+1,c1,l2,c2)); for(i=c1;i<c2;++i) dp[l1][c1][l2][c2]=min(dp[l1][c1][l2][c2],dpr(l1,c1,l2,i)+dpr(l1,i+1,l2,c2)); dp[l1][c1][l2][c2]+=sp[l2][c2]-sp[l2][c1-1]-sp[l1-1][c2]+sp[l1-1][c1-1]; return dp[l1][c1][l2][c2]; } void write() { cout<<dpr(1,1,N,M); } int main() { read(); precalc(); write(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...