Submission #101090

#	Time	Username	Problem	Language	Result	Execution time	Memory
101090		choikiwon	K-th path (IZhO11_kthpath)	C++17	0 / 100	17 ms	716 KiB

kthpath

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll comb[33][33];

int N, M;
ll K;
char G[33][33];
string ans;

ll cc[33][33][33];
ll dp(int r, int c, int x) {
    ll &ret = cc[r][c][x];
    if(ret != -1) return ret;

    ret = 0;
    if(G[r][c] != ans[x]) return ret;
    if(x == (int)ans.size() - 1) return ret = comb[N + M - 2 - r - c][M - 1 - c];
    if(r < N) ret += dp(r + 1, c, x + 1);
    if(c < M) ret += dp(r, c + 1, x + 1);
    return ret;
}

ll calc() {
    memset(cc, -1, sizeof(cc));
    return dp(0, 0, 0);
}

int main() {
    comb[0][0] = 1;
    for(int i = 1; i < 33; i++) {
        comb[i][0] = 1;
        for(int j = 1; j <= i; j++) {
            comb[i][j] = comb[i - 1][j - 1] + comb[i - 1][j];
        }
    }

    std::ios::sync_with_stdio(false);

    cin >> N >> M;

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> G[i][j];
        }
    }

    cin >> K;

    for(int i = 0; i < N + M; i++) {
        for(int j = 0; j < 26; j++) {
            ans.push_back('a' + j);

            ll t = calc();
            if(K <= t) break;
            K -= t;
            ans.pop_back();
        }
    }

    cout << ans;
}

• Subtask 1: 0 / 100