Submission #102175

#TimeUsernameProblemLanguageResultExecution timeMemory
102175IvanCMobitel (COCI19_mobitel)C++17
91 / 130
3077 ms66560 KiB
#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; vector<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]; 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(); while(ptr[0] < sz[0] || ptr[1] < sz[1]){ ii element = ii(-1, -1); if(ptr[0] == sz[0]){ if(paths[a[1]][b[1]][ptr[1]].first > max_value){ ptr[1] = sz[1]; continue; } element = paths[a[1]][b[1]][ptr[1]]; ptr[1]++; } else if(ptr[1] == sz[1]){ if(paths[a[0]][b[0]][ptr[0]].first > max_value){ ptr[0] = sz[0]; continue; } element = paths[a[0]][b[0]][ptr[0]]; ptr[0]++; } else if(paths[a[0]][b[0]][ptr[0]] <= paths[a[1]][b[1]][ptr[1]]){ if(paths[a[0]][b[0]][ptr[0]].first > max_value){ ptr[0] = sz[0]; continue; } element = paths[a[0]][b[0]][ptr[0]]; ptr[0]++; } else{ if(paths[a[1]][b[1]][ptr[1]].first > max_value){ ptr[1] = sz[1]; continue; } element = paths[a[1]][b[1]][ptr[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(int i = 0;i < paths[x][y].size();i++){ paths[x][y][i].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++){ vector<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 (stderr)

mobitel.cpp: In function 'void in_place_merge(int, int, int, int)':
mobitel.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < paths[x][y].size();i++){
                ~~^~~~~~~~~~~~~~~~~~~~
mobitel.cpp: In function 'int main()':
mobitel.cpp:141: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:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&matriz[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...