제출 #231687

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231687		AlexLuchianov	건포도 (IOI09_raisins)	C++14	100 / 100	244 ms	26464 KiB

raisins

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 50;
ll const inf = 1000000000000000000;
ll dp[1 + nmax][1 + nmax][1 + nmax][1 + nmax];
int v[1 + nmax][1 + nmax], sum[1 + nmax][1 + nmax];

int getsum(int x, int y, int x2, int y2){
  return sum[x2][y2] - sum[x - 1][y2] - sum[x2][y - 1] + sum[x - 1][y - 1];
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 1;i <= n; i++)
    for(int j = 1;j <= m; j++) {
      cin >> v[i][j];
      sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + v[i][j];
    }

  for(int dif = 0; dif < n; dif++)
    for(int i = 1; i <= n - dif; i++)
      for(int dif2 = 0; dif2 < m; dif2++)
        for(int i2 = 1; i2 <= m - dif2; i2++){
          int j = i + dif;
          int j2 = i2 + dif2;
          dp[i][j][i2][j2] = inf;
          if(i == j && i2 == j2) {
            dp[i][j][i2][j2] = 0;
            continue;
          }
          ll basic = getsum(i, i2, j, j2);

          for(int k = i; k < j; k++)
            dp[i][j][i2][j2] = min(dp[i][j][i2][j2], dp[i][k][i2][j2] + dp[k + 1][j][i2][j2] + basic);
          for(int k = i2; k < j2; k++)
            dp[i][j][i2][j2] = min(dp[i][j][i2][j2], dp[i][j][i2][k] + dp[i][j][k + 1][j2] + basic);
        }
  cout << dp[1][n][1][m];
  return 0;
}

• Subtask 1: 100 / 100