제출 #1127751

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127751		VMaksimoski008	K번째 경로 (IZhO11_kthpath)	C++20	100 / 100	1 ms	328 KiB

kthpath

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;

vector<pii> G[35][35];
ll dp[35][35];
int bad[35][35];

signed main() {
    int n, m; cin >> n >> m;
    string ans = "";

    char mat[n+1][m+1];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++) cin >> mat[i][j];
    
    ll K; cin >> K;
    ans += mat[1][1];
    for(int it=2; it<=n+m-1; it++) {
        int l=0, r=25, pos=25;
        while(l <= r) {
            int mid = (l + r) / 2;
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++) dp[i][j] = 0;

            dp[1][1] = 1;
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                    if(bad[i][j]) continue;
                    if(i + j - 2 == it - 1 && mat[i][j] - 'a' > mid) continue;
                    dp[i][j] += dp[i-1][j] + dp[i][j-1];
                }
            }

            if(dp[n][m] >= K) pos = mid, r = mid - 1;
            else l = mid + 1;
        }

        if(pos) {
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++) dp[i][j] = 0;
            dp[1][1] = 1;

            for(int i=1; i<=n; i++) {
                for(int j=1; j<=m; j++) {
                    if(bad[i][j]) continue;
                    if(i + j - 2 == it - 1 && mat[i][j] - 'a' > pos - 1) continue;
                    dp[i][j] += dp[i-1][j] + dp[i][j-1];
                }
            }

            K -= dp[n][m];
        }

        char ch = 'a' + pos;
        ans += ch;
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                if(i + j - 2 == it - 1 && mat[i][j] != ch) bad[i][j] = 1;
    }

    cout << ans << '\n';
    return 0;
}

• Subtask 1: 100 / 100