#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN = 302;
const int MOD = 1e9 + 7;
list<ii> paths[2][MAXN];
int matriz[MAXN][MAXN],dp[MAXN][MAXN],R,S,N, current_x;
ll tot;
ll fast_expo(ll x, ll y){
if(y == 0) return 1;
if(y % 2 == 0){
ll temp = fast_expo(x, y/2);
return (temp*temp) % MOD;
}
else{
return (x*fast_expo(x, y - 1)) % MOD;
}
}
ll mod_inv(ll x){
return fast_expo(x, MOD - 2);
}
ll fatorial(int n){
ll ans = 1;
for(int i = 2;i<=n;i++){
ans = (ans * i) % MOD;
}
return ans;
}
ll binomial(int n, int k){
ll ans = (fatorial(n) * mod_inv(fatorial(k)) ) % MOD;
ans = (ans * mod_inv(fatorial(n - k))) % MOD;
return ans;
}
void in_place_merge(int x, int y, int factor, int second_factor){
int max_value = N/second_factor;
int ptr[2], a[2], b[2], sz[2];
list<ii>::iterator it[2];
ptr[0] = ptr[1] = 0;
a[0] = x, a[1] = x ^ 1;
b[0] = y - 1, b[1] = y;
sz[0] = paths[a[0]][b[0]].size(), sz[1] = paths[a[1]][b[1]].size();
it[0] = paths[a[0]][b[0]].begin(), it[1] = paths[a[1]][b[1]].begin();
while(ptr[0] < sz[0] || ptr[1] < sz[1]){
ii element = ii(-1, -1);
if(ptr[0] == sz[0]){
if((*it[1]).first > max_value){
ptr[1] = sz[1];
continue;
}
element = *it[1];
it[1]++;
ptr[1]++;
}
else if(ptr[1] == sz[1]){
if((*it[0]).first > max_value){
ptr[0] = sz[0];
continue;
}
element = *it[0];
it[0]++;
ptr[0]++;
}
else if((*it[0]) <= (*it[1])){
if((*it[0]).first > max_value){
ptr[0] = sz[0];
continue;
}
element = *it[0];
it[0]++;
ptr[0]++;
}
else{
if((*it[1]).first > max_value){
ptr[1] = sz[1];
continue;
}
element = *it[1];
it[1]++;
ptr[1]++;
}
if(paths[x][y].empty() || paths[x][y].back().first != element.first){
paths[x][y].push_back(element);
}
else{
paths[x][y].back().second = (paths[x][y].back().second + element.second) % MOD;
}
}
for(list<ii>::iterator nit = paths[x][y].begin();nit != paths[x][y].end();nit++){
(*nit).first *= factor;
}
}
int solve(int x,int y){
if(dp[x][y] != 0) return dp[x][y];
if(x == R && y == S) return matriz[x][y];
ll cand;
if(x + 1 <= R && y + 1 <= S){
cand = 1LL*matriz[x][y]*min(solve(x+1,y), solve(x, y + 1));
}
else if(x + 1 <= R){
cand = 1LL*matriz[x][y]*solve(x+1,y);
}
else{
cand = 1LL*matriz[x][y]*solve(x,y+1);
}
if(cand <= N){
return dp[x][y] = cand;
}
else{
return dp[x][y] = N+1;
}
}
int main(){
scanf("%d %d %d", &R, &S, &N);
N--;
for(int i = 1;i<=R;i++){
for(int j = 1;j<=S;j++){
scanf("%d",&matriz[i][j]);
}
}
if(matriz[1][1] <= N) paths[current_x][1].push_back(ii(matriz[1][1], 1));
for(int i = 2;i<=S;i++){
in_place_merge(current_x, i, matriz[1][i], solve(1, i));
}
for(int i = 2;i <= R;i++){
current_x ^= 1;
for(int j = 1;j<=S;j++) list<ii>().swap(paths[current_x][j]);
for(int j = 1;j<=S;j++){
in_place_merge(current_x, j, matriz[i][j], solve(i, j));
}
}
ll ans = binomial(R + S - 2, S - 1);
for(ii davez : paths[current_x][S]){
ans = ans - davez.second;
ans %= MOD;
}
if(ans < 0) ans += MOD;
printf("%lld\n",ans);
return 0;
}
Compilation message
mobitel.cpp: In function 'int main()':
mobitel.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &R, &S, &N);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:152:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&matriz[i][j]);
~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
723 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
24 ms |
1016 KB |
Output is correct |
| 3 |
Correct |
536 ms |
7488 KB |
Output is correct |
| 4 |
Correct |
447 ms |
6460 KB |
Output is correct |
| 5 |
Runtime error |
1413 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
431 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Correct |
102 ms |
3324 KB |
Output is correct |
| 8 |
Runtime error |
182 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
194 ms |
66560 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Execution timed out |
6089 ms |
56952 KB |
Time limit exceeded |
