fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define BIT(x , i) ((x >> i) & 1)
  3.  
  4. using namespace std;
  5. int const N = 12 ;
  6. int S ;
  7. int a[N][N] ;
  8. int T[N][N][N][N][N] ;
  9. long long dp[N][N][N][N][N][N] ;
  10. long long CALC(int id, int h1, int h2, int h3, int h4, int h5, int lim)
  11. {
  12.     if(id > 10) return 1 ;
  13.     long long res = dp[id][h1][h2][h3][h4][h5] ;
  14.     if(res != -1) return res ;
  15.     res = 0 ;
  16.     for(int tmp = 0 ; tmp <= 31 ; tmp ++)
  17.     {
  18.         int t1, t2, t3, t4, t5 ;
  19.         bool ok = true ;
  20.         for(int i = 0 ; i < 5 ; i ++) if(BIT(tmp, i) == 0 && a[id][i + 1] == 1) ok = false ;
  21.         if(ok == false) continue ;
  22.         t1 = h1 + 1 ;
  23.         t2 = h2 + 1 ;
  24.         t3 = h3 + 1 ;
  25.         t4 = h4 + 1 ;
  26.         t5 = h5 + 1 ;
  27.         if(BIT(tmp, 0) == 1) t1 = 0 ;
  28.         if(BIT(tmp, 1) == 1) t2 = 0 ;
  29.         if(BIT(tmp, 2) == 1) t3 = 0 ;
  30.         if(BIT(tmp, 3) == 1) t4 = 0 ;
  31.         if(BIT(tmp, 4) == 1) t5 = 0 ;
  32.         if(T[t1][t2][t3][t4][t5] <= lim) res += CALC(id + 1, t1, t2, t3, t4, t5, lim) ;
  33.     }
  34.     dp[id][h1][h2][h3][h4][h5] = res ;
  35.     return res ;
  36. }
  37. int MAXS(int h1, int h2, int h3, int h4, int h5)
  38. {
  39.     int h[N], L[N], R[N] ;
  40.     h[1] = h1, h[2] = h2, h[3] = h3, h[4] = h4, h[5] = h5 ;
  41.     h[0] = h[6] = -1 ;
  42.     L[1] = 1 ;
  43.     for(int i = 2 ; i <= 5 ; i ++)
  44.     {
  45.         L[i] = i ;
  46.         while(h[L[i] - 1] >= h[i]) L[i] = L[L[i] - 1] ;
  47.     }
  48.     R[5] = 5 ;
  49.     for(int i = 4 ; i >= 1 ; i --)
  50.     {
  51.         R[i] = i ;
  52.         while(h[R[i] + 1] >= h[i]) R[i] = R[R[i] + 1] ;
  53.     }
  54.     int tmp = 0 ;
  55.     for(int i = 1 ; i <= 5 ; i ++) tmp = max(tmp, (R[i] - L[i] + 1) * h[i]) ;
  56.     return tmp ;
  57. }
  58. void INIT()
  59. {
  60.     for(int i = 0 ; i <= 10 ; i ++)
  61.         for(int j = 0 ; j <= 10 ; j ++)
  62.             for(int k = 0 ; k <= 10 ; k ++)
  63.                 for(int p = 0 ; p <= 10 ; p ++)
  64.                     for(int q = 0 ; q <= 10 ; q ++) T[i][j][k][p][q] = MAXS(i, j, k, p, q) ;
  65. }
  66. int main()
  67. {
  68.     ios_base::sync_with_stdio(NULL) ;
  69.     cin.tie(0) ;
  70.     cout.tie(0) ;
  71.     cin >> S ;
  72.     for(int i = 1 ; i <= 5 ; i ++)
  73.         for(int j = 1 ; j <= 10 ; j ++)
  74.         {
  75.             char c ;
  76.             cin >> c ;
  77.             a[j][i] = c - '0' ;
  78.         }
  79.     INIT() ;
  80.     memset(dp, -1, sizeof(dp)) ;
  81.     long long ans1 = CALC(1, 0, 0, 0, 0, 0, S) ;
  82.     memset(dp, - 1, sizeof(dp)) ;
  83.     long long ans2 = CALC(1, 0, 0, 0, 0, 0, S - 1) ;
  84.     cout << ans1 - ans2 ;
  85.     return 0;
  86. }
Success #stdin #stdout 0.02s 27852KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/2RqsLB
language:
C++14 (gcc 8.3)
created:
7 days 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!