Submission #102525

#TimeUsernameProblemLanguageResultExecution timeMemory
102525NnandiMobitel (COCI19_mobitel)C++14
0 / 130
218 ms66560 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxrs = 305; const int maxme = 1005; const ll mod = 1000000007LL; ll dpkis[maxrs][maxrs][maxme]; ll dpnagy[maxrs][maxrs][maxme]; ll tab[maxrs][maxrs]; int r, s; ll n, m; int main() { cin>>r>>s>>n; m = (ll)sqrt(n); for(int i=0;i<r;i++) { for(int j=0;j<s;j++) { cin>>tab[i][j]; } } for(int c=1;c<=min(tab[0][0],m);c++) { dpkis[0][0][c] = 1LL; } for(int i=0;i<r;i++) { for(int j=0;j<s;j++) { for(int c=1;c<=m;c++) { int req = (int)max(1LL,(c + tab[i][j] - 1) / tab[i][j]); dpkis[i][j][c] += (i > 0 ? dpkis[i-1][j][req] : 0LL); dpkis[i][j][c] += (j > 0 ? dpkis[i][j-1][req] : 0LL); dpkis[i][j][c] %= mod; } } } for(int i=0;i<r;i++) { for(int j=0;j<s;j++) { for(int c=1;c<=m;c++) { if(i == 0 && j == 0 && n <= c) dpnagy[i][j][c] = 1LL; if(c * tab[i][j] > m) { int prereq = (n+c-1) / c; int req = (prereq + tab[i][j] - 1) / tab[i][j]; dpnagy[i][j][c] += (i > 0 ? dpkis[i-1][j][req] : 0LL); dpnagy[i][j][c] += (j > 0 ? dpkis[i][j-1][req] : 0LL); dpnagy[i][j][c] %= mod; } else { int req = c * tab[i][j]; dpnagy[i][j][c] += (i > 0 ? dpnagy[i-1][j][req] : 0LL); dpnagy[i][j][c] += (j > 0 ? dpnagy[i][j-1][req] : 0LL); dpnagy[i][j][c] %= mod; } } } } cout<<dpnagy[r-1][s-1][1]<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...