Submission #333768

#	Time	Username	Problem	Language	Result	Execution time	Memory
333768		limabeans	K-th path (IZhO11_kthpath)	C++17	100 / 100	1 ms	364 KiB

kthpath

#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][maxn+maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    for (int i=0; i<maxn+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;
}

• Subtask 1: 100 / 100