Submission #683362

#	Time	Username	Problem	Language	Result	Execution time	Memory
683362		nifeshe	K-th path (IZhO11_kthpath)	C++17	100 / 100	2 ms	340 KiB

kthpath

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e6;
const int lg = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            char c;
            cin >> c;
            a[i][j] = c - 'a';
        }
    }
    vector<vector<int>> dp(n, vector<int>(m));
    dp[n - 1][m - 1] = 1;
    for(int i = n - 1; ~i; i--) {
        for(int j = m - 1; ~j; j--) {
            if(i) dp[i - 1][j] += dp[i][j];
            if(j) dp[i][j - 1] += dp[i][j];
        }
    }
    int k;
    cin >> k; k--;
    string ans;
    vector<vector<int>> dp_back(n, vector<int>(m)), ndp_back(n, vector<int>(m));
    ans.pb(char('a' + a[0][0]));
    dp_back[0][0] = 1;
    for(int it = 1; it < n + m - 1; it++) {
        //cnt prefix == ans
        vector<int> cnt(26);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(i + 1 < n) cnt[a[i + 1][j]] += dp_back[i][j] * dp[i + 1][j];
                if(j + 1 < m) cnt[a[i][j + 1]] += dp_back[i][j] * dp[i][j + 1];
            }
        }
        int add = 0;
        while(cnt[add] <= k) k -= cnt[add++];
        ans.pb(char('a' + add));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(i + 1 < n && a[i + 1][j] == add) ndp_back[i + 1][j] += dp_back[i][j];
                if(j + 1 < m && a[i][j + 1] == add) ndp_back[i][j + 1] += dp_back[i][j];
            }
        }
        dp_back = ndp_back;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                ndp_back[i][j] = 0;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
//    freopen("kthpath.in", "r", stdin); freopen("kthpath.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

• Subtask 1: 100 / 100