oj.uz

Submission #225945

# Submission time Handle Problem Language Result Execution time Memory
225945 2020-04-22T04:19:25 Z balbit Abduction 2 (JOI17_abduction2) C++14
27 / 100
 138 ms 63232 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 3e5+5;

int dp[2002][2002][2][2];
int A[2002],B[2002];

signed main(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<pair<int, pii> > ss;
    for (int i = 0 ;i<n; ++i) {
        cin>>A[i];
        ss.pb({A[i], {i, 0}});
    }
    for (int j = 0; j<m; ++j) {
        cin>>B[j];
        ss.pb({B[j], {j, 1}});
    }

    sort(ALL(ss), greater<pair<int, pii>>());

    for (auto & ele : ss) {
        int P = ele.s.f;
        int V = ele.f;
        bug(V);
        if (ele.s.s == 0) {
            for (int i = m-1; i>=0; --i) {
                if (B[i] > V) {
                    dp[P][i][0][1] = max(dp[P][i][1][0], dp[P][i][1][1]);
                }else{
                    dp[P][i][0][1] = i==m-1?0:1+dp[P][i+1][0][1];
                }
            }
            for (int i = 0; i<m; ++i) {
                if (B[i] > V) {
                    dp[P][i][0][0] = max(dp[P][i][1][0], dp[P][i][1][1]);
                }else{
                    dp[P][i][0][0] = i==0?0:1+dp[P][i-1][0][0];
                }
            }
        }else{
            for (int i = n-1; i>=0; --i) {
                if (A[i] > V) {
                    dp[i][P][1][1] = max(dp[i][P][0][0], dp[i][P][0][1]);
                }else{
                    dp[i][P][1][1] = i==n-1?0:1+dp[i+1][P][1][1];
                }
            }
            for (int i = 0; i<n; ++i) {
                if (A[i] > V) {
                    dp[i][P][1][0] = max(dp[i][P][0][0], dp[i][P][0][1]);
                }else{
                    dp[i][P][1][0] = i==0?0:1+dp[i-1][P][1][0];
                }
            }
        }
    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][0][0]<<" \n"[j==m-1];
//    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][1][0]<<" \n"[j==m-1];
//    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][0][1]<<" \n"[j==m-1];
//    }
//    for (int i = 0; i<n; ++i) for (int j = 0; j<m; ++j) {
//        cout<<dp[i][j][1][1]<<" \n"[j==m-1];
//    }
    while (q--) {
        int a,b; cin>>a>>b; --a; --b;
        int re = 0;
        if (a) re = max(re, dp[a-1][b][1][0]);
        if (b) re = max(re, dp[a][b-1][0][0]);
        if (a!=n-1) re = max(re, dp[a+1][b][1][1]);
        if (b!=m-1) re = max(re, dp[a][b+1][0][1]);
        cout<<re+1<<endl;
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 119 ms 63232 KB Output is correct
13 Correct 118 ms 63220 KB Output is correct
14 Correct 115 ms 63228 KB Output is correct
15 Correct 138 ms 63104 KB Output is correct
16 Correct 124 ms 63224 KB Output is correct
17 Correct 104 ms 63224 KB Output is correct
18 Correct 102 ms 63096 KB Output is correct
19 Correct 117 ms 63096 KB Output is correct
20 Correct 112 ms 61304 KB Output is correct
21 Correct 115 ms 63224 KB Output is correct
22 Correct 109 ms 63224 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 119 ms 63232 KB Output is correct
13 Correct 118 ms 63220 KB Output is correct
14 Correct 115 ms 63228 KB Output is correct
15 Correct 138 ms 63104 KB Output is correct
16 Correct 124 ms 63224 KB Output is correct
17 Correct 104 ms 63224 KB Output is correct
18 Correct 102 ms 63096 KB Output is correct
19 Correct 117 ms 63096 KB Output is correct
20 Correct 112 ms 61304 KB Output is correct
21 Correct 115 ms 63224 KB Output is correct
22 Correct 109 ms 63224 KB Output is correct
23 Runtime error 79 ms 4456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 63204 KB Output is correct
2 Correct 127 ms 63224 KB Output is correct
3 Correct 126 ms 63224 KB Output is correct
4 Correct 124 ms 63200 KB Output is correct
5 Correct 117 ms 63104 KB Output is correct
6 Correct 101 ms 63152 KB Output is correct
7 Correct 100 ms 63224 KB Output is correct
8 Correct 108 ms 63096 KB Output is correct
9 Correct 107 ms 62072 KB Output is correct
10 Correct 105 ms 63096 KB Output is correct
11 Correct 120 ms 63084 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 4 ms 384 KB Output is correct
12 Correct 119 ms 63232 KB Output is correct
13 Correct 118 ms 63220 KB Output is correct
14 Correct 115 ms 63228 KB Output is correct
15 Correct 138 ms 63104 KB Output is correct
16 Correct 124 ms 63224 KB Output is correct
17 Correct 104 ms 63224 KB Output is correct
18 Correct 102 ms 63096 KB Output is correct
19 Correct 117 ms 63096 KB Output is correct
20 Correct 112 ms 61304 KB Output is correct
21 Correct 115 ms 63224 KB Output is correct
22 Correct 109 ms 63224 KB Output is correct
23 Runtime error 79 ms 4456 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -