# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
333767 | limabeans | K-th path (IZhO11_kthpath) | C++17 | 1 ms | 492 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>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 33;
const ll inf = 1e18 + 10;
void add(ll &x, ll y) {
x += y;
x = min(x, inf);
}
ll mul(ll x, ll y) {
if (x > inf/y) return inf;
return x*y;
}
int n, m;
ll dp[maxn][maxn];
vector<pair<int,int>> diag[maxn+maxn];
string g[maxn];
ll k;
ll C[maxn][maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for (int i=0; i<maxn; i++) {
C[i][0]=C[i][i]=1;
for (int j=1; j<i; j++) {
add(C[i][j], C[i-1][j]);
add(C[i][j], C[i-1][j-1]);
}
}
assert(C[4][2]==6);
cin>>n>>m;
for (int i=1; i<=n; i++) {
cin>>g[i];
g[i]="*"+g[i];
}
for (int i=1; i<=n; i++) {
for (int j=1; j<=m; j++) {
diag[i+j].push_back({i,j});
}
}
cin>>k;
dp[1][1] = 1;
cout<<g[1][1];
for (int d=3; d<=n+m; d++) {
vector<ll> w(26, 0);
for (auto p: diag[d]) {
int i = p.first; int j = p.second;
int down = n-i; int right = m-j;
add(w[g[i][j]-'a'], mul(min(inf, dp[i-1][j]+dp[i][j-1]), C[down+right][right]));
}
for (int let=0; let<26; let++) {
if (k > w[let]) {
k -= w[let];
continue;
}
cout<<char('a'+let);
for (auto p: diag[d]) {
int i = p.first; int j = p.second;
if (int(g[i][j]-'a')==let) {
add(dp[i][j], min(inf, dp[i-1][j]+dp[i][j-1]));
}
}
break;
}
}
cout<<endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |