fork download
copy 
  1. //// "و ذا النون اذ ذهب مغاضبا فظن ان لن نقدر عليه"
  2. //// "فنادي في الظلمات ان لا اله لا انت سبحانك اني كنت من الظالمين"
  3. ////  "فاستجبنا له و نجينه من الغم و كذلك ننجي المؤمنين"
  4. // MORE FALLS , HIGHER JUMPS YOU GET !! //
  5.  
  6. #include <bits/stdc++.h>
  7. #define ll long long
  8. #define Zhraa ios_base::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr);
  9. #define YES "YES"
  10. #define NO "NO"
  11. #define sp ' '
  12. #define nl '\n'
  13. #define ON(mask,bit) (mask | (1LL<<bit) )
  14. #define OFF(mask,bit) ( mask & ~ ( 1LL << bit ) )
  15. #define IsOn(mask,bit) (( mask>>bit) & 1LL)
  16. #define toggle(mask,bit)( mask ^ (1LL<<bit) )
  17. #define IsOdd(mask) (mask & 1LL)
  18. using namespace std;
  19.  
  20. #include <ext/pb_ds/assoc_container.hpp>
  21. #include <ext/pb_ds/tree_policy.hpp>
  22. #include <cstring>
  23. using namespace __gnu_pbds;
  24. #define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
  25.  
  26.  
  27. //        down   up right  left
  28. int dx []={ 1 , -1 , 0 ,  0     , -1 ,1,-1, 1 };
  29. int dy []={ 0 ,  0 , 1 , -1     , -1 ,1, 1,-1 };
  30. char dir[] = {'D', 'U' , 'R' , 'L'};
  31.  
  32. const ll MOD = 1e9 + 7;
  33. const int N = 500 + 3 ;
  34. const int oo = 0x3f3f3f3f;
  35. const ll ooLL = 0x3f3f3f3f3f3f3f3f;
  36.  
  37. ///////////////////////////////////////// The Code ///////////////////////////////////////////
  38.  
  39. // constant
  40. // state
  41. int a,b;
  42. ll  dp [N][N];
  43. ll go (int i,int j){ // calc min moves to get sqrs from dimensions
  44.  
  45.     if(i==1&&j==1)
  46.         return 1;
  47.     if(~dp[i][j])
  48.         return dp[i][j];
  49.  
  50.     ll ans = ooLL;
  51.     if(i!=1){
  52.         for (int k = 1; k < i; ++k) {// cuting vertical
  53.             ll op1 = go(k, j)%MOD;
  54.             ll op2 = go(i - k, j);
  55.             if(k==i-k)
  56.                 ans = min(ans, op1);
  57.             else
  58.                 ans= min(ans,op1+op2);
  59.         }
  60.     }
  61.  
  62.     if(j!=1){
  63.         for (int k = 1; k < j; ++k) {//cutting horizontal
  64.             ll op1 = go(i, k);
  65.             ll op2 = go(i, j - k);
  66.             if(k==j-k)
  67.                 ans = min(ans, op1);
  68.             else
  69.                 ans= min(ans,op1+op2);
  70.         }
  71.     }
  72.  
  73.     return dp[i][j]=ans;
  74. }
  75.  
  76.  
  77. void solve(){
  78.     cin>>a>>b;
  79.     memset(dp,-1,sizeof dp);
  80.     cout<<go(a,b);
  81.  
  82. }
  83.  
  84.  
  85. int main() {
  86.  
  87. #ifndef ONLINE_JUDGE
  88.     freopen("input.txt", "r", stdin);
  89.     freopen("output.txt", "w", stdout);
  90. #endif
  91.  
  92.     Zhraa
  93.  
  94.     int t =1;
  95.     //cin>>t;
  96.  
  97.     while (t--)
  98.         solve();
  99.  
  100.  
  101. }
  102.  
Success #stdin #stdout 0.01s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4557430888798830399
https://ideone.com/GT4wSt
language:
C++14 (gcc 8.3)
created:
23 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!