fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define mset(arr,x) memset(arr,x,sizeof(arr))
  6. #define rep(i,s,e) for(i=s;i<=e;i++)
  7. #define rrep(i,s,e) for(i=s;i>=e;i--)
  8.  
  9. string st[110];
  10. ll N, M, res;
  11. ll dp[110][110][110];
  12. bool check[110][110][110];
  13. ll func( ll row, ll col, ll K )
  14. {
  15.     if( K==0 )
  16.     {
  17.         return 0;
  18.     }
  19.     if( dp[row][col][K]!=-1 )
  20.     {
  21.         return dp[row][col][K];
  22.     }
  23.  
  24.     ll i, j, ans = 0, val = 0;
  25.     for(i=0; (row+i)<=N; i++)
  26.     {
  27.         if( (col-i)>=1 && (col+i)<=M && check[row+i][col-i][col+i] )
  28.         {
  29.            val += (2*i)+1;
  30.            ll opop = -1, opop2;
  31.            for(j=(col-i); j<=(col+i); j++)
  32.            {
  33.               opop2 = -1;
  34.               if( (row+i)<N && st[row+1+i][j]=='#' )
  35.               {
  36.                 opop2 = func(row+i+1, j, K-1);
  37.               }
  38.               opop = max(opop, opop2);
  39.            }
  40.            if( opop>0 )
  41.               ans = max(ans, val+opop);
  42.         }
  43.         else
  44.         {
  45.            break;
  46.         }
  47.     }
  48.     if( K==1 )
  49.     {
  50.         ans = max(ans, val);
  51.     }
  52.  
  53.     dp[row][col][K] = ans;
  54.     return dp[row][col][K];
  55. }
  56. int main()
  57. {
  58.     ll i, j, k, K, T, ppll;
  59.  
  60.     cin >> T;
  61.     rep(ppll, 1, T)
  62.     {
  63.        res = 0;
  64.        mset(check, 0);
  65.        mset(dp, -1);
  66.  
  67.        cin >> N >> M >> K;
  68.        rep(i, 1, N)
  69.        {
  70.            cin >> st[i];
  71.            st[i] = "@" + st[i];
  72.        }
  73.  
  74.        rep(i, 1, N)
  75.        {
  76.            rep(j, 1, M)
  77.            {
  78.                rep(k, j, M)
  79.                {
  80.                    if( j!=k )
  81.                    {
  82.                      check[i][j][k] = (check[i][j][k-1] && (st[i][k]=='#'));
  83.                    }
  84.                    else
  85.                    {
  86.                      check[i][j][k] = (st[i][k]=='#');
  87.                    }
  88.                }
  89.            }
  90.        }
  91.  
  92.        rep(i, 1, N)
  93.        {
  94.            rep(j, 1, M)
  95.            {
  96.                if( st[i][j]=='#' )
  97.                {
  98.                    func(i, j, K);
  99.                    res = max(res, dp[i][j][K]);
  100.                }
  101.            }
  102.        }
  103.  
  104.        cout << "Case #" << ppll << ": ";
  105.        cout << res << endl;
  106.     }
  107.  
  108.     return 0;
  109. }
  110.  
Success #stdin #stdout 0s 27752KB
comments (?)
stdin 
4
3 5 1
..#..
.###.
#####
3 5 1
.....
.....
.....
4 5 1
#####
#####
#####
#####
4 5 2
#####
#####
#####
#####
stdout 
Case #1: 9
Case #2: 0
Case #3: 9
Case #4: 10
https://ideone.com/ZAOpvy
language:
C++14 (gcc 8.3)
created:
7 years 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!