oj.uz

Submission #488971

# Submission time Handle Problem Language Result Execution time Memory
488971 2021-11-20T23:22:38 Z SirCovidThe19th K-th path (IZhO11_kthpath) C++17
100 / 100
 1 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define f first
#define s second

int n, m; ll k, ways[35][35], choose[75][75]; string A[35];
pll range[35][35], par[35][35];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> A[i], A[i] = " " + A[i];
    cin >> k;

    for (int i = 0; i < 75 and (choose[i][0] = 1); i++)
        for (int j = 1; j <= i; j++)
            choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1];

    ways[1][1] = 1; range[1][1] = {1, choose[n + m - 2][n - 1]}; 

    for (int len = 2; len <= n + m - 1; len++){
        unordered_map<ll, vector<pll>> mp;
        for (int i = min(len, n), j = max(len - n + 1, 1); i and j <= m; i--, j++){
            if (ways[i - 1][j]) range[i][j] = range[i - 1][j], par[i][j] = {i - 1, j};
            if (ways[i][j - 1]) range[i][j] = range[i][j - 1], par[i][j] = {i, j - 1};
            ways[i][j] += ways[i - 1][j] + ways[i][j - 1];
            if (ways[i][j]) mp[range[i][j].f].push_back({i, j});
        }
        for (auto X : mp){
            vector<pll> V = X.s; ll rangeST = X.f; 
            for (char c = 'a'; c <= 'z'; c++){
                ll tot = 0;
                for (pll i : V) if (A[i.f][i.s] == c){
                    tot += ways[i.f][i.s] * choose[(n - i.f) + (m - i.s)][(m - i.s)];
                }
                for (pll i : V) if (A[i.f][i.s] == c){
                    range[i.f][i.s] = {rangeST, rangeST + tot - 1};
                    if (k < rangeST or k > rangeST + tot - 1) ways[i.f][i.s] = 0;
                }
                rangeST += tot;
            }
        }
    }
    vector<char> ans; pll cur = {n, m};
    while (cur.f) ans.push_back(A[cur.f][cur.s]), cur = par[cur.f][cur.s];
    for (int i = ans.size() - 1; ~i; i--) cout<<ans[i];
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 312 KB Output is correct
6 Correct 0 ms 336 KB Output is correct
7 Correct 0 ms 336 KB Output is correct
8 Correct 0 ms 336 KB Output is correct
9 Correct 0 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 308 KB Output is correct
13 Correct 0 ms 312 KB Output is correct
14 Correct 0 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 0 ms 336 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 0 ms 336 KB Output is correct
20 Correct 0 ms 336 KB Output is correct