Submission #100869

#TimeUsernameProblemLanguageResultExecution timeMemory
100869cki86201K-th path (IZhO11_kthpath)C++11
100 / 100
3 ms512 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <iostream> #include <functional> #include <unordered_set> #include <bitset> #include <time.h> #include <limits.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define Fi first #define Se second #define pb(x) push_back(x) #define szz(x) (int)x.size() #define rep(i,n) for(int i=0;i<n;i++) #define all(x) x.begin(),x.end() typedef tuple<int, int, int> t3; int N, M; ll C[32][32], Co[72][72]; char X[32][32]; ll K; int main() { rep(i, 72) { Co[i][0] = 1; for(int j=1;j<=i;j++) Co[i][j] = Co[i-1][j-1] + Co[i-1][j]; } scanf("%d%d", &N, &M); for(int i=1;i<=N;i++) scanf("%s", X[i] + 1); scanf("%lld", &K); C[1][1] = 1; string ans; ans.pb(X[1][1]); for(int a=2;a<N+M;a++) { vector <pair<char, pii> > P; for(int x=1;x<=N;x++) { int y = a - x; if(1 <= y && y <= M) { if(x < N) C[x+1][y] += C[x][y]; if(y < M) C[x][y+1] += C[x][y]; } } ll cnt[30] = {}; for(int x=1;x<=N;x++) { int y = a + 1 - x; if(1 <= y && y <= M) { cnt[X[x][y]-'a'] += C[x][y] * Co[N-x+M-y][N-x]; P.pb(make_pair(X[x][y], pii(x, y))); } } char f = -1; for(int i=0;i<30;i++) { if(K > cnt[i]) K -= cnt[i]; else { f = 'a' + i; break; } } ans.pb(f); rep(i, szz(P)) if(P[i].Fi != f) C[P[i].Se.Fi][P[i].Se.Se] = 0; } printf("%s\n", ans.c_str()); return 0; }

Compilation message (stderr)

kthpath.cpp: In function 'int main()':
kthpath.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
kthpath.cpp:43:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%s", X[i] + 1);
                        ~~~~~^~~~~~~~~~~~~~~~
kthpath.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &K);
  ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...