oj.uz

Submission #481289

# Submission time Handle Problem Language Result Execution time Memory
481289 2021-10-20T08:27:00 Z FatihSolak K-th path (IZhO11_kthpath) C++17
100 / 100
 1 ms 332 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct