fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define ll long long
  6. #define bit(n, i) ((n >> i) & 1)
  7. #define all(a) a.begin(), a.end()
  8. #define rep(i, x, n) for (int i = x; i <= n; ++i)
  9. #define red(i, x, n) for (int i = x; i >= n; --i)
  10. #define inp(a) if (fopen(a".inp", "r")) freopen(a".inp", "r", stdin), freopen(a".out", "w", stdout)
  11.  
  12. template<class A, class B> inline bool maxi(A &x, B y) {return (x < y ? x = y, 1 : 0);};
  13. template<class A, class B> inline bool mini(A &x, B y) {return (x > y ? x = y, 1 : 0);};
  14.  
  15. const int N = 2e6 + 5;
  16. const ll MOD = 1e9 + 7;
  17. const ll INF = LLONG_MAX;
  18.  
  19. // main program
  20.  
  21. int n, m, d;
  22. int a[N], f[N];
  23. int preD[N], preR[N];
  24. int Down[N], Right[N];
  25.  
  26. int ID(int u, int v){
  27.     return u * (m + 1) + v;
  28. }
  29.  
  30. void add(int &x, int y){
  31.     if (y < 0) y += MOD;
  32.     x += y;
  33.     if (x >= MOD) x -= MOD;
  34. }
  35. signed main(){
  36.     cin.tie(0) -> sync_with_stdio(0);
  37.     inp("JUMP");
  38.     cin >>n >>m >>d;
  39.  
  40.     rep(i, 1, n) rep(j, 1, m){
  41.         char c; cin >>c;
  42.         a[ID(i, j)] = c - '0';
  43.     }
  44.  
  45.     rep(i, 1, n) rep(j, 1, m){
  46.         Right[ID(i, j)] = Right[ID(i, j - 1)] + a[ID(i, j)];
  47.     }
  48.  
  49.     rep(j, 1, m) rep(i, 1, n){
  50.         Down[ID(i, j)] = Down[ID(i - 1, j)] + a[ID(i, j)];
  51.     }
  52.  
  53.     f[ID(1, 1)] = 1;
  54.     preR[ID(1, 1)] = preD[ID(1, 1)] = f[ID(1, 1)];
  55.  
  56.     rep(i, 1, n) rep(j, 1, m){
  57.         if (i == 1 && j == 1) continue;
  58.  
  59.         int l, r, p;
  60.  
  61.         l = 1, r = j - 1, p = -1;
  62.  
  63.         while (l <= r){
  64.             int mid = l + r >> 1;
  65.  
  66.             if (Right[ID(i, j)] - Right[ID(i, mid - 1)] <= d){
  67.                 p = mid; r = mid - 1;
  68.             } else l = mid + 1;
  69.         }
  70.  
  71.         if (p != -1){
  72.             add(f[ID(i, j)], preR[ID(i, j - 1)] - preR[ID(i, p - 1)]);
  73.         }
  74.  
  75.         l = 1, r = i - 1, p = -1;
  76.  
  77.         while (l <= r){
  78.             int mid = l + r >> 1;
  79.  
  80.             if (Down[ID(i, j)] - Down[ID(mid - 1, j)] <= d){
  81.                 p = mid; r = mid - 1;
  82.             } else l = mid + 1;
  83.         }
  84.  
  85.         if (p != -1){
  86.             add(f[ID(i, j)], preD[ID(i - 1, j)] - preD[ID(p - 1, j)]);
  87.         }
  88.  
  89.         preR[ID(i, j)] = f[ID(i, j)];
  90.         preD[ID(i, j)] = f[ID(i, j)];
  91.         add(preR[ID(i, j)], preR[ID(i, j - 1)]);
  92.         add(preD[ID(i, j)], preD[ID(i - 1, j)]);
  93.     }
  94.  
  95.     cout <<f[ID(n, m)];
  96.  
  97.     return 0;
  98. }
Success #stdin #stdout 0.01s 9776KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/m3vrcs
language:
C++ (gcc 8.3)
created:
3 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!