Guest User

Untitled

a guest
Jan 9th, 2020
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  5. #define INF LLONG_MAX
  6. #define MOD 20011
  7.  
  8. int main()
  9. {
  10.     fastio;
  11.  
  12.     ll r,c,d,w,y,flag = 0;
  13.     vector<vector<ll>> dpleft(305, vector<ll>(305));
  14.     vector<vector<ll>> dpup(305, vector<ll>(305));
  15.     vector<vector<ll>> blockedornot(305, vector<ll>(305));
  16.  
  17.     cin >> r >> c >> d;
  18.  
  19.     for( ll i = 1 ; i <= r ; i++)
  20.     {
  21.         for( ll j = 1; j <= c ; j++)
  22.         {
  23.             cin >> blockedornot[i][j];
  24.         }
  25.     }
  26.  
  27.     dpleft[1][1] = 1;
  28.     dpup[1][1] = 1;
  29.  
  30.     if( r== 1 && c == 1)
  31.     {
  32.         cout << 1;
  33.         return 0;
  34.     }
  35.  
  36.     for( ll i = 2 ; i <= d+1 ; i++)
  37.     {
  38.         if( blockedornot[1][i] == 0 ) break;
  39.         else
  40.         {
  41.             dpleft[1][i] = 1;
  42.         }
  43.     }
  44.  
  45.     for( ll i = 2 ; i <= d+1 ; i++)
  46.     {
  47.         if( blockedornot[i][1] == 0 ) break;
  48.         else
  49.         {
  50.             dpup[i][1] = 1;
  51.         }
  52.     }
  53.  
  54.     for( ll i = 2 ; i <= r ; i++)
  55.     {
  56.         for( ll j = 2 ; j <= c ; j++)
  57.         {
  58.             flag = 0;
  59.             if( blockedornot[i][j] == 1)
  60.             {
  61.                 dpleft[i][j] = dpleft[i][j-1] + dpup[i][j-1];
  62.                 dpleft[i][j] = (dpleft[i][j])%MOD;
  63.  
  64.                 if( j-d-1 >= 1)
  65.                 {
  66.                     for( ll k = j-d-1 ; k <= j-1 ; k++)
  67.                     {
  68.                         if( blockedornot[i][k] == 0)
  69.                         {
  70.                             flag = 1;
  71.                             break;
  72.                         }
  73.                     }
  74.                 }
  75.  
  76.                 if( j-d-1 >= 1 && flag != 1)
  77.                 {
  78.                     y = dpleft[i][j] - dpup[i][j-d-1];
  79.                     dpleft[i][j] = max((ll)0, y)%MOD;
  80.                 }
  81.  
  82.                 flag = 0;
  83.  
  84.  
  85.                 dpup[i][j] = dpleft[i-1][j] + dpup[i-1][j] ;
  86.                 dpup[i][j] = (dpup[i][j])%MOD;
  87.  
  88.                 if( i-d-1 >= 1)
  89.                 {
  90.                     for( ll k = i-d-1 ; k <= i-1 ; k++)
  91.                     {
  92.                         if( blockedornot[k][j] == 0)
  93.                         {
  94.                             flag = 1;
  95.                             break;
  96.                         }
  97.                     }
  98.                 }
  99.  
  100.                 if( i-d-1 >= 1  && flag != 1)
  101.                 {
  102.                     y = dpup[i][j] - dpleft[i-d-1][j];
  103.                     dpup[i][j] = max( (ll)0 ,y )%MOD;
  104.                 }
  105.  
  106.             }
  107.         }
  108.     }
  109.  
  110.     w = (dpleft[r][c] + dpup[r][c])%MOD;
  111.  
  112.     cout << w << "\n";
  113. //
  114. //    for( ll i = 1 ; i <= r ; i++)
  115. //    {
  116. //        for( ll j = 1; j <= c ; j++)
  117. //        {
  118. //           cout << dpleft[i][j] << "\t";
  119. //        }
  120. //        cout << "\n";
  121. //    }
  122. //
  123. //    cout << endl;
  124. //
  125. //    for( ll i = 1 ; i <= r ; i++)
  126. //    {
  127. //        for( ll j = 1; j <= c ; j++)
  128. //        {
  129. //           cout << dpup[i][j] << "\t";
  130. //        }
  131. //        cout << "\n";
  132. //    }
  133.  
  134.     return 0;
  135. }
Add Comment
Please, Sign In to add comment