# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
100869 | cki86201 | K-th path (IZhO11_kthpath) | C++11 | 3 ms | 512 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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;
int N, M;
ll C[32][32], Co[72][72];
char X[32][32];
ll K;
int main() {
rep(i, 72) {
Co[i][0] = 1;
for(int j=1;j<=i;j++) Co[i][j] = Co[i-1][j-1] + Co[i-1][j];
}
scanf("%d%d", &N, &M);
for(int i=1;i<=N;i++) scanf("%s", X[i] + 1);
scanf("%lld", &K);
C[1][1] = 1;
string ans; ans.pb(X[1][1]);
for(int a=2;a<N+M;a++) {
vector <pair<char, pii> > P;
for(int x=1;x<=N;x++) {
int y = a - x;
if(1 <= y && y <= M) {
if(x < N) C[x+1][y] += C[x][y];
if(y < M) C[x][y+1] += C[x][y];
}
}
ll cnt[30] = {};
for(int x=1;x<=N;x++) {
int y = a + 1 - x;
if(1 <= y && y <= M) {
cnt[X[x][y]-'a'] += C[x][y] * Co[N-x+M-y][N-x];
P.pb(make_pair(X[x][y], pii(x, y)));
}
}
char f = -1;
for(int i=0;i<30;i++) {
if(K > cnt[i]) K -= cnt[i];
else { f = 'a' + i; break; }
}
ans.pb(f);
rep(i, szz(P)) if(P[i].Fi != f) C[P[i].Se.Fi][P[i].Se.Se] = 0;
}
printf("%s\n", ans.c_str());
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |