# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
895688 | raul2008487 | K-th path (IZhO11_kthpath) | C++17 | 2033 ms | 600 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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.
*/
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |