oj.uz

Submission #282196

# Submission time Handle Problem Language Result Execution time Memory
282196 2020-08-24T06:21:46 Z 최은수(#5756) Abduction 2 (JOI17_abduction2) C++17
0 / 100
 248 ms 94852 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
int a[50010],b[50010];
ll dp[2010][2010];
ll dp1[2010][2010],dp2[2010][2010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int h,w,q;
    cin>>h>>w>>q;
    for(int i=0;i++<h;)
        cin>>a[i];
    for(int i=0;i++<w;)
        cin>>b[i];
    vector<pi>sv;
    for(int i=0;i++<h;)
        sv.eb(a[i],i);
    for(int i=0;i++<w;)
        sv.eb(b[i],i+h);
    sort(all(sv),greater<pi>());
    for(pi&t:sv)
    {
        if(t.se>h)
        {
            int c=t.se-h;
            {
                ll cur=0;
                for(int j=0;j++<h;)
                {
                    if(a[j]>b[c])
                        cur=dp[j][c];
                    else
                        dp[j][c]=max(dp[j][c],dp1[j][c]=cur);
                    cur++;
                }
            }
            {
                ll cur=0;
                for(int j=h;j>0;j--)
                {
                    if(a[j]>b[c])
                        cur=dp[j][c];
                    else
                        dp[j][c]=max(dp[j][c],dp2[j][c]=cur);
                    cur++;
                }
            }
        }
        else
        {
            int c=t.se;
            {
                ll cur=0;
                for(int j=0;j++<w;)
                {
                    if(b[j]>a[c])
                        cur=dp[c][j];
                    else
                        dp[c][j]=max(dp[c][j],dp1[j][c]=cur);
                    cur++;
                }
            }
            {
                ll cur=0;
                for(int j=w;j>0;j--)
                {
                    if(b[j]>a[c])
                        cur=dp[c][j];
                    else
                        dp[c][j]=max(dp[c][j],dp2[j][c]=cur);
                    cur++;
                }
            }
        }
    }
    for(int i=0;i<q;i++)
    {
        int x,y;
        cin>>x>>y;
        ll ans=0;
        if(x!=1)
            ans=max(ans,1+(a[x-1]>b[y]?dp[x-1][y]:dp1[x-1][y]));
        if(y!=1)
            ans=max(ans,1+(a[x]>b[y-1]?dp1[x][y-1]:dp[x][y-1]));
        if(x!=h)
            ans=max(ans,1+(a[x+1]>b[y]?dp[x+1][y]:dp2[x+1][y]));
        if(y!=w)
            ans=max(ans,1+(a[x]>b[y+1]?dp2[x][y+1]:dp[x][y+1]));
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 94852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 0 ms 384 KB Output isn't correct
11 Halted 0 ms 0 KB -