제출 #1286609

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

kthpath

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define sz(x) (int)(x).size()

const int N = (int) 30;
const int dx[] = {0 , 1};
const int dy[] = {1 , 0};

int numrow , numcol;
LL need_k;
LL C[N * 2 + 2][N * 2 + 2] , cnt[26] = {};
LL dp[N * 2 + 2][N + 2][N + 2] = {};
char a[N + 2][N + 2];

vector<pair<int,int>> pos[26] = {};
void reset(){
    for(int i = 0; i < 26; ++i) pos[i].clear();
    for(int i = 0; i < 26; ++i) cnt[i] = 0;
    return;
}
LL ways(int start_x , int start_y){
    int t1 = numrow - start_x + 1;
    int t2 = numcol - start_y + 1;
    return C[t1 + t2 - 2][t2 - 1];
}

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

    cin >> numrow >> numcol;
    for(int i = 1; i <= numrow; ++i){
        for(int j = 1; j <= numcol; ++j) cin >> a[i][j];
    }
    cin >> need_k;

    for(int i = 0; i <= numrow + numcol - 1; ++i) C[i][0] = 1;
    for(int i = 1; i <= numrow + numcol - 1; ++i){
        for(int j = 1; j <= i; ++j){
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }

    vector<pair<int,int>> cur_pos;
    cur_pos.push_back({1 , 1});
    dp[0][1][1] = 1;
    string ans = "";
    for(int st = 1; st <= numrow + numcol - 1; ++st){
        ans += a[cur_pos[0].first][cur_pos[0].second];
        reset();
//        cout << st << '\n';
//        for(auto& x : cur_pos) cout << x.first << ' ' << x.second << '\n';

        for(auto& x : cur_pos){
            for(int t = 0; t < 2; ++t){
                int nxt_u = x.first + dx[t];
                int nxt_v = x.second + dy[t];
                if (nxt_u <= numrow && nxt_v <= numcol){
                    pos[a[nxt_u][nxt_v] - 'a'].push_back({nxt_u , nxt_v});
                    cnt[a[nxt_u][nxt_v] - 'a'] += dp[st - 1][x.first][x.second] * ways(nxt_u , nxt_v);
                    dp[st][nxt_u][nxt_v] += dp[st - 1][x.first][x.second];
                }
            }
        }

        for(int i = 0; i < 26; ++i){
            sort(pos[i].begin() , pos[i].end());
            pos[i].resize(unique(pos[i].begin() , pos[i].end()) - pos[i].begin());
            if (need_k <= cnt[i]){
                cur_pos = pos[i];
                break;
            }
            need_k -= cnt[i];
        }
    }
    cout << ans;

    return 0;
}

• Subtask 1: 100 / 100