Submission #1223655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223655		MarwenElarbi	유괴 2 (JOI17_abduction2)	C++20	44 / 100	5092 ms	16592 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;

int h , w , q;
const int H = 5e4;
unordered_map<int , int> dp[2][H + 1];
int a[H + 1] , b[H + 1];
// 0 : --
// 1 : |

int dfs(int i , int j , int dir)
{
    if(dp[dir][i].find(j) != dp[dir][i].end())
    {
        return dp[dir][i][j];
    }
    dp[dir][i][j]=0;
    if(dir == 0)
    {
        int k = j + 1;
        int val=a[i];
        for(; k < w ; k++)
        {
            if(b[k] > val)
            {
                break;
            }
        }
        int k_ = j - 1 ;
        for(;k_ >= 0 ;k_--)
        {
            if(b[k_] > val)
            {
                break;
            }
        }
        if(b[k] > val)
        {
            dp[dir][i][j] = dfs(i , k , dir^1) + k - j;
        }
        else
        {
            dp[dir][i][j] = k - j;
        }
        if(b[k_] > val){
            dp[dir][i][j]= max (dp[dir][i][j] , dfs(i,k_,dir^1) + j - k_);
        }
        else 
        {
            dp[dir][i][j]= max( dp[dir][i][j] , j - k_ );
        }
    }
    else
    {
        int k = i + 1;
        int val=b[j];
        for(; k < h ; k++)
        {
            if(a[k] > val)
            {
                break;
            }
        }
        int k_ =i - 1 ;
        for(;k_ >= 0 ;k_--)
        {
            if(a[k_] > val)
            {
                break;
            }
        }
        if(a[k] > val)
        {
            dp[dir][i][j] = dfs(k , j , dir^1) + k - i;
        }
        else
        {
            dp[dir][i][j] = k - i;
        }
        if(a[k_] > val){
            dp[dir][i][j]= max (dp[dir][i][j] , dfs(k_,j,dir^1) + i - k_);
        }
        else
        {
            dp[dir][i][j] = max(dp[dir][i][j] , i - k_);
        }
    }
    return dp[dir][i][j];
}
//a[i=3] = 5: - - |b[j=3]=7 - - |b[j=8]=19 - - : 7 , 19  N 

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>h>>w>>q;
    for (int i=0; i<h; i++) {
        cin>>a[i];
    }
    for (int i=0; i<w; i++) {
        cin>>b[i];
    }
    while(q--){
        for(int dir = 0 ; dir < 2 ; dir++)
        {
            for(int i = 0 ; i <= H ;i++)
            {
                dp[dir][i].clear();
            }
        }
        int x,y;
        cin>>x>>y;
        x--;y--;
        cout << max(dfs(x,y,0),dfs(x,y,1))-1 <<'\n';
    }
}

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