oj.uz

Submission #895693

# Submission time Handle Problem Language Result Execution time Memory
895693 2023-12-30T14:29:13 Z raul2008487 K-th path (IZhO11_kthpath) C++17
100 / 100
 2 ms 456 KB 
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define in insert
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int mod = 998244353;
ll can[35][35], used[35][35];
char a[35][35];
//bool used[35][35];
vector<char> v(66, '#');
ll n, m;
ll rec(ll x, ll y){
    if(x > n || y > m){return 0;}
    if(v[x + y - 2] == a[x][y]){
        if(v[x + y - 1] == '#'){return can[x][y];}
        if(used[x][y] != -1){
            return used[x][y];
        }
        ll ret = rec(x+1, y) + rec(x, y+1);
        return used[x][y] = ret;
    }
    return 0;
}
void solve()
{
    ll i, j, k;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        can[i][m] = 1;
        for(j=1;j<=m;j++){
            can[n][j] = 1;
            cin>>a[i][j];
        }
    }
    cin>>k;
    for(i = n-1; i>0; i--){
        for(j = m-1; j>0; j--){
            can[i][j] = can[i+1][j] + can[i][j+1];
        }
    }
    v[0] = a[1][1];
    for(i=1;i<(n+m-1);i++){
        for(j = 'a'; j <= 'z'; j++){
            v[i] = char(j);
            memset(used, -1, sizeof(used));
            ll dk = rec(1, 1);
            if(dk >= k){
                ///cout << i << ' ' << char(j) << ' ' << dk << endl;
                break;
            }
            k -= dk;
        }
        if(k <= 0){
            break;
        }
    }
    string final = "";
    for(i=0;i<(n+m-1);i++){
        final += v[i];
    }
    cout << final << endl;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //precomp();
    ll tst=1;
    //cin>>tst;
    while(tst--){
            solve();
    }
}
/*
ok.
*/

Subtask #1
100.0 / 100.0

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