oj.uz

Submission #282197

# Submission time Handle Problem Language Result Execution time Memory
282197 2020-08-24T06:22:51 Z 최은수(#5756) Abduction 2 (JOI17_abduction2) C++17
27 / 100
 218 ms 94968 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[c][j]=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[c][j]=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
13.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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 488 KB Output is correct
10 Correct 1 ms 416 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #2
10.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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 488 KB Output is correct
10 Correct 1 ms 416 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 209 ms 94840 KB Output is correct
13 Correct 203 ms 94964 KB Output is correct
14 Correct 210 ms 94840 KB Output is correct
15 Correct 205 ms 94900 KB Output is correct
16 Correct 211 ms 94840 KB Output is correct
17 Correct 175 ms 94840 KB Output is correct
18 Correct 177 ms 94840 KB Output is correct
19 Correct 184 ms 94840 KB Output is correct
20 Correct 179 ms 91896 KB Output is correct
21 Correct 195 ms 94820 KB Output is correct
22 Correct 185 ms 94968 KB Output is correct

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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 488 KB Output is correct
10 Correct 1 ms 416 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 209 ms 94840 KB Output is correct
13 Correct 203 ms 94964 KB Output is correct
14 Correct 210 ms 94840 KB Output is correct
15 Correct 205 ms 94900 KB Output is correct
16 Correct 211 ms 94840 KB Output is correct
17 Correct 175 ms 94840 KB Output is correct
18 Correct 177 ms 94840 KB Output is correct
19 Correct 184 ms 94840 KB Output is correct
20 Correct 179 ms 91896 KB Output is correct
21 Correct 195 ms 94820 KB Output is correct
22 Correct 185 ms 94968 KB Output is correct
23 Runtime error 29 ms 3192 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 94896 KB Output is correct
2 Correct 218 ms 94968 KB Output is correct
3 Correct 207 ms 94840 KB Output is correct
4 Correct 206 ms 94968 KB Output is correct
5 Correct 214 ms 94968 KB Output is correct
6 Correct 179 ms 94840 KB Output is correct
7 Correct 178 ms 94944 KB Output is correct
8 Correct 185 ms 94840 KB Output is correct
9 Correct 177 ms 93176 KB Output is correct
10 Correct 182 ms 94840 KB Output is correct
11 Correct 180 ms 94840 KB Output is correct

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 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 488 KB Output is correct
10 Correct 1 ms 416 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 209 ms 94840 KB Output is correct
13 Correct 203 ms 94964 KB Output is correct
14 Correct 210 ms 94840 KB Output is correct
15 Correct 205 ms 94900 KB Output is correct
16 Correct 211 ms 94840 KB Output is correct
17 Correct 175 ms 94840 KB Output is correct
18 Correct 177 ms 94840 KB Output is correct
19 Correct 184 ms 94840 KB Output is correct
20 Correct 179 ms 91896 KB Output is correct
21 Correct 195 ms 94820 KB Output is correct
22 Correct 185 ms 94968 KB Output is correct
23 Runtime error 29 ms 3192 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -