oj.uz

Submission #895688

# Submission time Handle Problem Language Result Execution time Memory
895688 2023-12-30T14:16:15 Z raul2008487 K-th path (IZhO11_kthpath) C++17
0 / 100
 2000 ms 600 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];
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 - 2] != '#' && v[x + y - 1] == '#'){return can[x][y];}
        ll ret = rec(x+1, y) + rec(x, y+1);
        return 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);
            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
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 0 ms 460 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Execution timed out 2033 ms 344 KB Time limit exceeded
11 Halted 0 ms 0 KB -