Submission #1066268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066268		Unforgettablepl	Abduction 2 (JOI17_abduction2)	C++17	23 / 100	5020 ms	524288 KiB

abduction2

#pragma GCC optimize("Ofast","unroll-all-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int H,W,Q;
    cin >> H >> W >> Q;
    vector<int> A(H+1);
    for(int i=1;i<=H;i++)cin>>A[i];
    vector<int> B(W+1);
    for(int i=1;i<=W;i++)cin>>B[i];
    for(int i=1;i<=Q;i++) {
        int s,t;cin>>s>>t;
        int bestans = 0;
        vector visited(5,vector(H+1,vector<int>(W+1,-1)));
        function<int(int,int,int&,int&)> dfs = [&](int x,int y,int &parx,int &pary) {
            if(x<1 or x>H or y<1 or y>W)return -1;
            int pedge = 0;
            if(x>parx)pedge=1;
            else if(x<parx)pedge=2;
            else if(y>pary)pedge=3;
            else if(y<pary)pedge=4;
            if(visited[pedge][x][y]!=-1)return visited[pedge][x][y];
            int ans=0;
            if(A[x]>B[y]) {
                if(x!=parx or y-1!=pary)ans=max(dfs(x,y-1,x,y)+1,ans);
                if(x!=parx or y+1!=pary)ans=max(dfs(x,y+1,x,y)+1,ans);
            } else {
                if(x+1!=parx or y!=pary)ans=max(dfs(x+1,y,x,y)+1,ans);
                if(x-1!=parx or y!=pary)ans=max(dfs(x-1,y,x,y)+1,ans);
            }
            return visited[pedge][x][y]=ans;
        };
        bestans = max(bestans,dfs(s,t,s,t));
        if(A[s]>B[t]) {
            bestans=max(bestans,dfs(s-1,t,s,t)+1);
            bestans=max(bestans,dfs(s+1,t,s,t)+1);
        } else {
            bestans=max(bestans,dfs(s,t-1,s,t)+1);
            bestans=max(bestans,dfs(s,t+1,s,t)+1);
        }
        cout << bestans << '\n';
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 0 / 17
• Subtask 4: 0 / 4
• Subtask 5: 0 / 56