Submission #718340

#	Time	Username	Problem	Language	Result	Execution time	Memory
718340		Yell0	Raisins (IOI09_raisins)	C++17	100 / 100	117 ms	21408 KiB

raisins

#include <bits/stdc++.h>

using namespace std;
int N,M,a[52][52],pfs[52][52],dp[52][52][52][52];

int main() {
  ios::sync_with_stdio(0);cin.tie(0);
  cin>>N>>M;
  for(int i=1;i<=N;++i)
    for(int j=1;j<=M;++j) {
      cin>>a[i][j];
      pfs[i][j]=pfs[i-1][j]+pfs[i][j-1]-pfs[i-1][j-1]+a[i][j];
    }
  for(int i=1;i<=N;++i)
    for(int j=1;j<=M;++j)
      for(int k=1;k+i-1<=N;++k)
        for(int l=1;l+j-1<=M;++l) {
          if(i==1&&j==1) {
            dp[i][j][k][l]=0;
            continue;
          }
          dp[i][j][k][l]=INT_MAX;
          for(int c=1;c<i;++c) dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-c][j][k+c][l]+dp[c][j][k][l]);
          for(int c=1;c<j;++c) dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-c][k][l+c]+dp[i][c][k][l]);
          dp[i][j][k][l]+=pfs[k+i-1][l+j-1]-pfs[k-1][l+j-1]-pfs[k+i-1][l-1]+pfs[k-1][l-1];
        }
  cout<<dp[N][M][1][1]<<'\n';
  return 0;
}

• Subtask 1: 100 / 100