oj.uz

Submission #956804

# Submission time Handle Problem Language Result Execution time Memory
956804 2024-04-02T13:28:40 Z DeltaStruct Raisins (IOI09_raisins) C++17
5 / 100
 171 ms 118684 KB 
#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 < n;++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 <= n;++l) if (j+l!=2){
    for (int i(0);i <= n-j;++i) for (int k(0);k <= m-k;++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 < j;++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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Incorrect 0 ms 440 KB Output isn't correct
3 Runtime error 1 ms 348 KB Execution killed with signal 11
4 Incorrect 1 ms 344 KB Output isn't correct
5 Runtime error 1 ms 604 KB Execution killed with signal 11
6 Runtime error 1 ms 860 KB Execution killed with signal 11
7 Runtime error 1 ms 348 KB Execution killed with signal 6
8 Runtime error 4 ms 4700 KB Execution killed with signal 11
9 Runtime error 1 ms 348 KB Execution killed with signal 6
10 Runtime error 8 ms 9564 KB Execution killed with signal 11
11 Runtime error 7 ms 8104 KB Execution killed with signal 11
12 Runtime error 21 ms 21596 KB Execution killed with signal 11
13 Runtime error 34 ms 31836 KB Execution killed with signal 11
14 Runtime error 10 ms 11356 KB Execution killed with signal 11
15 Runtime error 1 ms 604 KB Execution killed with signal 6
16 Runtime error 1 ms 348 KB Execution killed with signal 6
17 Runtime error 1 ms 604 KB Execution killed with signal 6
18 Runtime error 1 ms 604 KB Execution killed with signal 6
19 Runtime error 171 ms 107572 KB Execution killed with signal 11
20 Runtime error 169 ms 118684 KB Execution killed with signal 11