# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
102528 | Nnandi | Mobitel (COCI19_mobitel) | C++14 | 1474 ms | 5760 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const int maxrs = 305;
const int maxme = 1005;
const ll mod = 1000000007LL;
ll dpkis[maxrs][maxme];
ll dpkisuj[maxrs][maxme];
ll dpnagy[maxrs][maxme];
ll dpnagyuj[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 i=0;i<r;i++) {
for(int j=0;j<s;j++) {
for(int c=1;c<=m;c++) {
int req = (int)max((ll)1,(c + tab[i][j] - 1) / tab[i][j]);
dpkisuj[j][c] = 0LL;
if(i==0 && j==0 && c<=tab[i][j]) dpkisuj[j][c] = 1LL;
dpkisuj[j][c] += (i > 0 ? dpkis[j][req] : 0LL);
dpkisuj[j][c] += (j > 0 ? dpkisuj[j-1][req] : 0LL);
dpkisuj[j][c] %= mod;
}
for(int c=1;c<=m;c++) {
if(c * tab[i][j] > m) {
int prereq = (n+c-1) / c;
int req = (prereq + tab[i][j] - 1) / tab[i][j];
dpnagyuj[j][c] = 0LL;
if(i == 0 && j == 0 && n <= c) dpnagyuj[j][c] = 1LL;
dpnagyuj[j][c] += (i > 0 ? dpkis[j][req] : 0LL);
dpnagyuj[j][c] += (j > 0 ? dpkisuj[j-1][req] : 0LL);
dpnagyuj[j][c] %= mod;
}
else {
int req = c * tab[i][j];
dpnagyuj[j][c] = 0LL;
if(i == 0 && j == 0 && n <= c) dpnagyuj[j][c] = 1LL;
dpnagyuj[j][c] += (i > 0 ? dpnagy[j][req] : 0LL);
dpnagyuj[j][c] += (j > 0 ? dpnagyuj[j-1][req] : 0LL);
dpnagyuj[j][c] %= mod;
}
}
}
swap(dpkis,dpkisuj);
swap(dpnagy,dpnagyuj);
}
cout<<dpnagy[s-1][1]<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |