Submission #642074

#TimeUsernameProblemLanguageResultExecution timeMemory
642074vovamrMobitel (COCI19_mobitel)C++17
130 / 130
3215 ms9640 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define ll long long #define ld long double #define sz(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() #define pb push_back #define mpp make_pair #define ve vector using namespace std; using namespace __gnu_pbds; template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const ll inf = 1e18; const int iinf = 1e9; typedef pair<ll, ll> pll; typedef pair<int, int> pii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); } template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); } constexpr int md = 1e9 + 7; constexpr int iv2 = (md + 1) / 2; inline int add(int a, int b) { if((a+=b)>=md)a-=md; return a; } inline int sub(int a, int b) { if((a-=b)<0)a+=md; return a; } inline int mul(int a, int b) { return 1ll*a*b%md; } inline int bp(int a, int n) { int res = 1; for (; n; n >>= 1, a = mul(a, a)) { if (n & 1) res = mul(res, a); } return res; } inline int inv(int a) { return bp(a, md - 2); } inline void solve() { int n, m, k; cin >> n >> m >> k; ve<ve<int>> a(n, ve<int> (m)); for (auto &i : a) for (auto &j : i) cin >> j, chmin(j, k); int Z = k + 10; ve<int> al, pos(Z); for (int i = 1; i < Z; ++i) { int v = (k + i - 1) / i; if (al.empty() || al.back() != v) { pos[v] = sz(al); al.pb(v); } } int s = sz(al); ve<ve<int>> dp(m, ve<int>(s)); dp[0][pos[(k + a[0][0] - 1) / a[0][0]]] = 1; for (int i = 0; i < n; ++i) { ve<ve<int>> f(m, ve<int>(s)); for (int j = 0; j < m; ++j) { for (int z = 0; z < s; ++z) { if (!dp[j][z]) continue; if (i + 1 < n) { int x = a[i + 1][j]; int d = pos[(al[z] + x - 1) / x]; f[j][d] = add(f[j][d], dp[j][z]); } if (j + 1 < m) { int x = a[i][j + 1]; int d = pos[(al[z] + x - 1) / x]; dp[j + 1][d] = add(dp[j + 1][d], dp[j][z]); } } } if (i + 1 < n) dp.swap(f); } cout << dp[m - 1][pos[1]]; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int q = 1; // cin >> q; while (q--) solve(); cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...