Submission #871677

#TimeUsernameProblemLanguageResultExecution timeMemory
871677Elvin_FritlK-th path (IZhO11_kthpath)C++17
0 / 100
0 ms504 KiB
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops") ///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; /// toto -> 1 #define pb push_back #define pii pair<int,int> #define pll pair<ll,ll> #define io \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define all(a) a.begin(),a.end() #define rep(k,i,n) for(int k=i;k<n;k++) #define repp(k,i,n) for(int k=n-1;k>=i;k--) #define rech(k) for(char k='a';k<='z';k++) #define SZ(a) (int)a.size() #define MX(a) *max_element(all(a)) #define MN(a) *min_element(all(a)) #define SM(a) accumulate(all(a),0LL) #define vi vector<int> #define vl vector<long long> #define vvl vector<vector<long long>> #define vvi vector<vector<int>> /// toto -> 2 const int mod = 1e9 + 7 , modd = 998244353; typedef long long ll; void F1(bool res) { if(res) { cout<<"Yes\n" ; } else { cout<<"No\n" ; } } struct mint{ ll val; mint(int64_t v = 0) { v %= mod; if (v < 0) v += mod; val = v; } mint& operator+=(const mint& other) { val += other.val; if (val >= mod) val -= mod; return *this; } mint& operator-=(const mint& other) { val += mod - other.val; if (val >= mod) val -= mod; return *this; } mint& operator*=(const mint& other) { val = (int64_t)val * other.val % mod; return *this; } mint& operator/=(const mint& other) { return *this *= other.inv(); } friend mint operator+(mint a, const mint& b) { return a += b; } friend mint operator-(mint a, const mint& b) { return a -= b; } friend mint operator*(mint a, const mint& b) { return a *= b; } friend mint operator/(mint a, const mint& b) { return a /= b; } mint pow(int64_t exp) const { mint a = *this, res = 1; while (exp > 0) { if (exp & 1) res *= a; a *= a; exp >>= 1; } return res; } mint inv() const { assert(val != 0); return pow(mod - 2); } friend ostream& operator<<(ostream& os, const mint& m) { return os << m.val; } }; ll bp(ll n,ll m){ if(m == 0){ return 1; } if(m == 1){ return n%mod; } if(m%2==0){ return bp(n*n%mod,m/2)%mod; } return n*bp(n,m-1)%mod; } /// toto -> 3 const int N = 2e5 + 544, M = 33, inf = 1e9 + 99; const ll inff = 1e18; int n,m,k; string res = ""; char c[M][M]; vvl dp(M , vl(M , -1)) , reset(M , vl(M , -1)); int func(int x, int y){ if (res[x + y] != c[x][y] && res[x + y]!='*'){ return 0; } if(x == n - 1 && y == m - 1){ return 1; } if(dp[x][y] != -1){ return dp[x][y]; } int tmp = 0; if(x + 1 < n){ tmp += func(x+1,y); } if(y+1<m){ tmp += func(x,y+1); } dp[x][y] = tmp; return tmp; } void solve(){ cin>>n>>m; rep(i,0,n){ rep(j,0,m){ cin>>c[i][j]; } } rep(i,0,n+m-1){ res += '*'; } cin>>k; res[0] = c[0][0]; rep(i,1,n+m-1){ rech(j){ res[i] = j; dp = reset; int x = func(0,0); if (x >= k){ break; } k -= x; } if(k <= 0){ break; } } cout << res << endl;; } int32_t main() { io; ll t=1; /// cin>>t; rep(_,1,t+1) { cerr << "Start of test case " << _ << "\n"; ///cout<<"Case #"<<_<<": "; solve(); cerr << endl; cerr << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...