Submission #963163

#	Time	Username	Problem	Language	Result	Execution time	Memory
963163		biank	K-th path (IZhO11_kthpath)	C++17	0 / 100	1 ms	348 KiB

kthpath

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 30;

using ll = __int128;

ll dp[MAX_N][MAX_N];
char g[MAX_N][MAX_N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    dp[n - 1][m - 1] = 1;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (i != n - 1) dp[i][j] += dp[i + 1][j];
            if (j != m - 1) dp[i][j] += dp[i][j + 1];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j];
        }
    }
    long long k;
    cin >> k;
    
    string ans = "";
    int i = 0, j = 0;
    while (i != n - 1 && j != m - 1) {
        ans += g[i][j];
        if (g[i + 1][j] < g[i][j + 1]) {
            if (k <= dp[i + 1][j]) i++;
            else k -= dp[i + 1][j], j++;
        } else {
            if (k <= dp[i][j + 1]) j++;
            else k -= dp[i][j + 1], i++;
        }
    }
    while (i != n - 1) ans += g[i][j], i++;
    while (j != m) ans += g[i][j], j++;
    cout << ans << '\n';
    
    return 0;
}

• Subtask 1: 0 / 100