Submission #956810

#	Time	Username	Problem	Language	Result	Execution time	Memory
956810		DeltaStruct	Raisins (IOI09_raisins)	C++17	100 / 100	267 ms	58964 KiB

raisins

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
signed main(){
  int n,m,inf=numeric_limits<int>::max(); cin >> n >> m;
  vector A(n+1,vector<int>(m+1)); for (int i(0);i < n;++i) for (int k(0);k < m;++k){
    cin>>A[i+1][k+1]; A[i+1][k+1] += A[i][k+1]+A[i+1][k]-A[i][k];
  }
  vector dp(n+1,vector(n+1,vector(m+1,vector<int>(m+1,inf))));
  for (int i(0);i < n;++i) for (int k(0);k < m;++k) dp[i][i+1][k][k+1] = 0;
  for (int j(1);j <= n;++j) for (int l(1);l <= m;++l) if (j+l!=2){
    for (int i(0);i <= n-j;++i) for (int k(0);k <= m-l;++k){
      int r = inf;
      for (int t(1);t < j;++t) r = min(r,dp[i][i+t][k][k+l]+dp[i+t][i+j][k][k+l]);
      for (int t(1);t < l;++t) r = min(r,dp[i][i+j][k][k+t]+dp[i][i+j][k+t][k+l]);
	    dp[i][i+j][k][k+l] = r+A[i+j][k+l]-A[i][k+l]-A[i+j][k]+A[i][k];
    }
  }
  cout << dp[0][n][0][m] << endl;
}

• Subtask 1: 100 / 100