제출 #481289

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

kthpath

#include <bits/stdc++.h>
#define N 35
using namespace std;
int n,m;
long long k;
char arr[N][N];
long long ways[N][N];
vector<pair<int,int>> dx = {{1,0},{0,1}};
bool ck(int a,int b){
    return a > 0 && a <= n && b > 0 && b <= m;
}
void solve(){
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> arr[i][j];
        }
    }
    ways[n][m] = 1;
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(i == n && j == m)continue;
            ways[i][j] = ways[i+1][j] + ways[i][j+1];
        }
    }
    cin >> k;
    cout << arr[1][1];
    vector<pair<int,int>> now;
    now.push_back({1,1});
    map<pair<int,int>,int> mp;
    mp[{1,1}] = 1;
    int tot = n+m-2;
    while(now[0].first != n || now[0].second != m){
        assert(now.size());
        set<pair<int,int>> nw;
        for(auto u:now){
            for(auto v:dx){
                if(ck(u.first + v.first,u.second + v.second)){
                    nw.insert({u.first + v.first,u.second + v.second});
                    mp[{u.first + v.first,u.second + v.second}]+= mp[u];
                }
            }
        }
        vector<long long> cnt(26);
        for(auto u:nw){
            if(ways[u.first][u.second] < 2e18/mp[u])
                cnt[arr[u.first][u.second] - 'a'] += ways[u.first][u.second] * mp[u];
            else cnt[arr[u.first][u.second] - 'a'] = 2e18;
            cnt[arr[u.first][u.second] - 'a'] = min(k,cnt[arr[u.first][u.second] - 'a']);
        }
        int num = 0;
        for(;num<26;num++){
            if(cnt[num] < k){
                k -= cnt[num];
            }
            else{
                cout << (char)(num + 'a');
                break;
            }
        }
        assert(num < 26);
        now.clear();
        for(auto u:nw){
            if(arr[u.first][u.second] - 'a' == num){
                now.push_back(u);
            }
        }
        assert(tot--);
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• Subtask 1: 100 / 100