oj.uz

Submission #101090

# Submission time Handle Problem Language Result Execution time Memory
101090 2019-03-16T12:52:23 Z choikiwon K-th path (IZhO11_kthpath) C++17
0 / 100
 17 ms 716 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 640 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 8 ms 640 KB Output is correct
7 Correct 9 ms 640 KB Output is correct
8 Correct 9 ms 640 KB Output is correct
9 Correct 9 ms 716 KB Output is correct
10 Incorrect 17 ms 640 KB Output isn't correct
11 Halted 0 ms 0 KB -