oj.uz

Submission #371251

# Submission time Handle Problem Language Result Execution time Memory
371251 2021-02-26T09:53:53 Z uacoder123 Raisins (IOI09_raisins) C++14
100 / 100
 1418 ms 58860 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) lli(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <ii,lli> iii;
typedef vector <lli> vi;
typedef tree<lli,null_type,less<lli>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
ii dp[50][50][50][50];
int arr[50][50],n,m;
ii cal(int r1,int c1,int r2,int c2)
{
  if(dp[r1][c1][r2][c2].F>0)
    return dp[r1][c1][r2][c2];
  if(r1==r2&&c1==c2)
  {
    dp[r1][c1][r2][c2]=mp(0,arr[r1][c1]);
    return dp[r1][c1][r2][c2];
  }
  dp[r1][c1][r2][c2]=mp(1000*25000000000000,10000000000*25000);
  for(int i=r1;i<r2;++i)
  {
    ii v1=cal(r1,c1,i,c2),v2=cal(i+1,c1,r2,c2);
    dp[r1][c1][r2][c2]=min(dp[r1][c1][r2][c2],mp(v1.F+v1.S+v2.F+v2.S,v1.S+v2.S));
  }
  for(int i=c2-1;i>=c1;--i)
  {
    ii v1=cal(r1,c1,r2,i),v2=cal(r1,i+1,r2,c2);
    dp[r1][c1][r2][c2]=min(dp[r1][c1][r2][c2],mp(v1.F+v1.S+v2.F+v2.S,v1.S+v2.S));
  }
  return dp[r1][c1][r2][c2];
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);\
  cin>>n>>m;
  for(int i=0;i<n;++i)
  {
    for(int j=0;j<m;++j)
    {
      cin>>arr[i][j];
    }
  }
  cout<<cal(0,0,n-1,m-1).F<<endl;
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 2 ms 1516 KB Output is correct
8 Correct 14 ms 4844 KB Output is correct
9 Correct 31 ms 7404 KB Output is correct
10 Correct 40 ms 8940 KB Output is correct
11 Correct 30 ms 7276 KB Output is correct
12 Correct 122 ms 16748 KB Output is correct
13 Correct 206 ms 22124 KB Output is correct
14 Correct 50 ms 9068 KB Output is correct
15 Correct 266 ms 24940 KB Output is correct
16 Correct 25 ms 8684 KB Output is correct
17 Correct 112 ms 18284 KB Output is correct
18 Correct 717 ms 43644 KB Output is correct
19 Correct 1231 ms 53828 KB Output is correct
20 Correct 1418 ms 58860 KB Output is correct