Submission #683293

#TimeUsernameProblemLanguageResultExecution timeMemory
683293vovamrK-th path (IZhO11_kthpath)C++17
0 / 100
2 ms596 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); } inline void solve() { /* #ifndef LOCAL const string NAME = "kthpath"; ifstream cin(NAME + ".in"); ofstream cout(NAME + ".out"); #endif */ int n, m; cin >> n >> m; ve<ve<char>> a(n, ve<char>(m)); for (auto &i : a) for (auto &j : i) cin >> j; ve<ve<ll>> dp(n, ve<ll> (m)); dp[n - 1][m - 1] = 1; for (int i = n - 1; ~i; --i) { for (int j = m - 1; ~j; --j) { if (i + 1 < n) dp[i][j] += dp[i + 1][j]; if (j + 1 < m) dp[i][j] += dp[i][j + 1]; } } ll k; cin >> k; string result(1, a[0][0]); map<string,ve<array<ll,3>>> cand; cand[string(1, a[0][0])] = {{dp[0][0], 0, 0}}; while (sz(result) < n + m - 1) { map<string,ve<array<ll,3>>> cur; string S = cand.begin()->fi; for (auto &[ways, x, y] : cand.begin()->se) { if (x + 1 < n) { cur[S + a[x + 1][y]].pb({dp[x + 1][y], x + 1, y}); } if (y + 1 < m) { cur[S + a[x][y + 1]].pb({dp[x][y + 1], x, y + 1}); } } map<string,ve<array<ll,3>>> nw; for (auto &[str, vec] : cur) { ll tot = 0; for (auto &[ways, x, y] : vec) tot += ways; if (k > tot) { k -= tot; } else { nw[str] = vec; break; } } swap(cand, nw); auto &vec = cand.begin()->se; ve<array<ll,3>> c; for (int i = 0; i < sz(vec); ++i) { if (!sz(c) || mpp(c.back()[1], c.back()[2]) != mpp(vec[i][1], vec[i][2])) c.pb(vec[i]); else c.back()[0] += vec[i][0]; } swap(vec, c); result = cand.begin()->fi; } cout << result; } 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...