Submission #103604

#TimeUsernameProblemLanguageResultExecution timeMemory
103604kishtarn555Mobitel (COCI19_mobitel)C++14
26 / 130
244 ms3840 KiB
#include<iostream> #include<math.h> #include<stdlib.h> #include<algorithm> using namespace std; int N,M, K; const long long mod = 1e9+7; long long mat[300][300]; long long memo[2][300][301]; long long memo2[2][300][301]; long long dp(int i, int j, long long s) { if (i < 0 ||j<0)return 0; s*=mat[i][j]; if ( s >= K)return 0; if (i==0 && j==0)return 1; return memo[i%2][j][s]; } long long dp2(int i, int j, long long s) { if (i < 0 ||j<0)return 0; if (i==0 || j==0)return 1; return memo2[i%2][j][s]; // return memo2[i][j][s] = (dp2(i-1,j,s)+dp2(i,j-1,s))%mod; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >>N>>M>>K; if (K>300)return 0; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { cin >> mat[i][j]; } } for (int i =0; i < N; i++){ for (int j =0; j < M; j++){ for (int s =1; s <= K; s++){ memo[i%2][j][s] = (dp(i-1,j,s)+dp(i,j-1,s))%mod; } memo2[i%2][j][1] = (dp2(i-1,j,1)+dp2(i,j-1,1))%mod; } } cout << (dp2(N-1,M-1,1)-dp(N-1,M-1,1)+mod)%mod; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...