| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 160059 | 2019-10-25T20:43:31 Z | RedNextCentury | Mobitel (COCI19_mobitel) | C++14 | 213 ms | 37752 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1000000007;
ll Power(ll a,ll b) {
if (b==0)return 1;
ll x = Power(a,b/2);
x = (x*x)%mod;
if (b%2)x=(x*a)%mod;
return x;
}
const int problemsettersIQ = 404; // not found
pair<int,int> dp[2][301][4001];
int len[2][301];
int a[problemsettersIQ][problemsettersIQ];
ll inv(ll x) {return Power(x,mod-2);}
int main()
{
//ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++) {
scanf("%d",&a[i][j]);
}
}
if (a[1][1]>k){
printf("0\n");
return 0;
}
dp[1][1][len[1][1]++]={a[1][1],1};
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if (i==1 && j==1)continue;
if (i==1){
for (int o=0;o<len[i%2][j-1];o++){
auto x = dp[i%2][j-1][o];
if (k/x.first < a[i][j])
break;
dp[i%2][j][len[i%2][j]++]={x.first*a[i][j],x.second};
}
}
else if (j==1){
for (int o=0;o<len[(i+1)%2][j];o++){
auto x = dp[(i+1)%2][j][o];
if (k/x.first < a[i][j])
break;
dp[i%2][j][len[i%2][j]++]={x.first*a[i][j],x.second};
}
}
else {
int l=0,r=0;
while(l<len[(i+1)%2][j] && r<len[i%2][j-1]) {
if (dp[(i+1)%2][j][l].first==dp[i%2][j-1][r].first) {
if (k/dp[(i+1)%2][j][l].first < a[i][j])break;
dp[i%2][j][len[i%2][j]++]={dp[(i+1)%2][j][l].first*a[i][j],(dp[(i+1)%2][j][l].second+dp[i%2][j-1][r].second)%mod};
l++,r++;
} else if (dp[(i+1)%2][j][l].first<dp[i%2][j-1][r].first) {
if (k/dp[(i+1)%2][j][l].first < a[i][j])break;
dp[i%2][j][len[i%2][j]++]={dp[(i+1)%2][j][l].first*a[i][j],dp[(i+1)%2][j][l].second};
l++;
} else {
if (k/dp[i%2][j-1][r].first < a[i][j])break;
dp[i%2][j][len[i%2][j]++]={dp[i%2][j-1][r].first*a[i][j],dp[i%2][j-1][r].second};
r++;
}
}
while(l<len[(i+1)%2][j]) {
if (k/dp[(i+1)%2][j][l].first < a[i][j])break;
dp[i%2][j][len[i%2][j]++]={dp[(i+1)%2][j][l].first*a[i][j],dp[(i+1)%2][j][l].second};
l++;
}
while(r<len[i%2][j-1]) {
if (k/dp[i%2][j-1][r].first < a[i][j])break;
dp[i%2][j][len[i%2][j]++]={dp[i%2][j-1][r].first*a[i][j],dp[i%2][j-1][r].second};
r++;
}
}
}
for (int j=1;j<=m;j++) len[(i+1)%2][j]=0;
}
ll ret=1;
for (int i=n+m-2 - (n-1) +1;i<=n+m-2;i++)ret=(ret*i)%mod;
for (int i=1;i<=(n-1);i++)ret=(ret*inv(i))%mod;
for (int o=0;o<len[n%2][m];o++) {
auto x = dp[n%2][m][o];
if (x.first>=k)break;
ret-=x.second;
ret+=mod;
ret%=mod;
}
printf("%lld\n",ret);
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 174 ms | 4216 KB | Output is correct |
| 2 | Correct | 184 ms | 4216 KB | Output is correct |
| 3 | Correct | 212 ms | 3248 KB | Output is correct |
| 4 | Correct | 213 ms | 3220 KB | Output is correct |
| 5 | Runtime error | 190 ms | 32632 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 | Runtime error | 125 ms | 25452 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 | Runtime error | 158 ms | 37752 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 | Runtime error | 154 ms | 27512 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 | Runtime error | 193 ms | 31864 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 | Runtime error | 51 ms | 19548 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |