Submission #336775

#TimeUsernameProblemLanguageResultExecution timeMemory
336775super_j6Abduction 2 (JOI17_abduction2)C++14
17 / 100
1389 ms524288 KiB
#include <iostream> #include <cstdio> #include <algorithm> #include <array> #include <unordered_map> using namespace std; #define endl '\n' #define ll long long #define pi pair<int, int> #define f first #define s second typedef array<int, 2> T; T operator+(T x, T y){ return {x[0] + y[0], x[1] + y[1]}; } const int mxn = 50000, k = 4; const T d[k] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; int n[2], q; int a[2][mxn]; unordered_map<ll, int> dp[k]; int sol(T x, int y){ for(int i = 0; i < 2; i++) if(x[i] < 0 || x[i] >= n[i]) return 0; ll f = (ll)x[0] * mxn + x[1]; if(dp[y].count(f)) return dp[y][f]; int ret = 0; if(a[!(y & 1)][x[!(y & 1)]] > a[y & 1][x[y & 1]]){ ret = sol(x + d[y], y); }else{ for(int i = 0; i < 2; i++){ int z = (y + 2 * i + 1) % k; ret = max(ret, sol(x + d[z], z)); } } return dp[y][f] = ++ret; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n[0] >> n[1] >> q; for(int i = 0; i < 2; i++) for(int j = 0; j < n[i]; j++){ cin >> a[i][j]; } while(q--){ T x; for(int i = 0; i < 2; i++) cin >> x[i], x[i]--; int ret = 0; for(int i = 0; i < k; i++) ret = max(ret, sol(x + d[i], i)); cout << ret << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...