oj.uz

Submission #241184

# Submission time Handle Problem Language Result Execution time Memory
241184 2020-06-23T08:21:23 Z osaaateiasavtnl Abduction 2 (JOI17_abduction2) C++17
27 / 100
 163 ms 64120 KB 
#include<bits/stdc++.h>
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 2007;

int a[N], b[N];
int dp[N][N][4];

struct State {
    int x, y, t;
    int val() {
        if (t&1)
            return a[x];
        else
            return b[y];
    };
    bool operator <(State s) {
        return val() < s.val();
    }
};  

int n, m, q;
int get(int x, int y, int t) {
    if (x < 0 || x >= n || y < 0 || y >= m) 
        return -1;

    if (dp[x][y][t] != -1)
        return dp[x][y][t];

    int &d = dp[x][y][t];
    d = 0;

    if (t&1) {
        if (a[x] < b[y]) {
            d = max(d, get(x,y,0));
            d = max(d, get(x,y,2));
        }
        else if (t == 1) {
            if (y + 1 < m)
                d = get(x,y+1,1)+1;
        }   
        else {
            if (y) 
                d = get(x,y-1,3)+1;
        }   
    }   
    else {
        if (b[y] < a[x]) {
            d = max(d, get(x,y,1));
            d = max(d, get(x,y,3));
        }   
        else if (t == 0) {
            if (x)
                d = get(x-1,y,0)+1;
        }
        else {
            if (x + 1 < n) 
                d = get(x+1,y,2)+1;
        }   
    }

    //cout << x << ' ' << y << ' ' << t << " : " << d << endl;
    return d;
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    cin >> n >> m >> q;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < m; ++i)
        cin >> b[i];
    
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < 4; ++k)
                dp[i][j][k] = -1;

    while (q--) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        int ans = 0;
        ans = max(ans, get(x-1,y,0)+1);
        ans = max(ans, get(x+1,y,2)+1);
        ans = max(ans, get(x,y-1,3)+1);
        ans = max(ans, get(x,y+1,1)+1);
        cout << ans << endl;
    }   
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63352 KB Output is correct
2 Correct 39 ms 63360 KB Output is correct
3 Correct 39 ms 63488 KB Output is correct
4 Correct 40 ms 63360 KB Output is correct
5 Correct 40 ms 63480 KB Output is correct
6 Correct 37 ms 63352 KB Output is correct
7 Correct 40 ms 63480 KB Output is correct
8 Correct 42 ms 63352 KB Output is correct
9 Correct 38 ms 63360 KB Output is correct
10 Correct 40 ms 63352 KB Output is correct
11 Correct 37 ms 63352 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63352 KB Output is correct
2 Correct 39 ms 63360 KB Output is correct
3 Correct 39 ms 63488 KB Output is correct
4 Correct 40 ms 63360 KB Output is correct
5 Correct 40 ms 63480 KB Output is correct
6 Correct 37 ms 63352 KB Output is correct
7 Correct 40 ms 63480 KB Output is correct
8 Correct 42 ms 63352 KB Output is correct
9 Correct 38 ms 63360 KB Output is correct
10 Correct 40 ms 63352 KB Output is correct
11 Correct 37 ms 63352 KB Output is correct
12 Correct 39 ms 63480 KB Output is correct
13 Correct 38 ms 63608 KB Output is correct
14 Correct 38 ms 63480 KB Output is correct
15 Correct 39 ms 63616 KB Output is correct
16 Correct 43 ms 63480 KB Output is correct
17 Correct 40 ms 63608 KB Output is correct
18 Correct 52 ms 63608 KB Output is correct
19 Correct 103 ms 63872 KB Output is correct
20 Correct 105 ms 63996 KB Output is correct
21 Correct 97 ms 63872 KB Output is correct
22 Correct 153 ms 63992 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63352 KB Output is correct
2 Correct 39 ms 63360 KB Output is correct
3 Correct 39 ms 63488 KB Output is correct
4 Correct 40 ms 63360 KB Output is correct
5 Correct 40 ms 63480 KB Output is correct
6 Correct 37 ms 63352 KB Output is correct
7 Correct 40 ms 63480 KB Output is correct
8 Correct 42 ms 63352 KB Output is correct
9 Correct 38 ms 63360 KB Output is correct
10 Correct 40 ms 63352 KB Output is correct
11 Correct 37 ms 63352 KB Output is correct
12 Correct 39 ms 63480 KB Output is correct
13 Correct 38 ms 63608 KB Output is correct
14 Correct 38 ms 63480 KB Output is correct
15 Correct 39 ms 63616 KB Output is correct
16 Correct 43 ms 63480 KB Output is correct
17 Correct 40 ms 63608 KB Output is correct
18 Correct 52 ms 63608 KB Output is correct
19 Correct 103 ms 63872 KB Output is correct
20 Correct 105 ms 63996 KB Output is correct
21 Correct 97 ms 63872 KB Output is correct
22 Correct 153 ms 63992 KB Output is correct
23 Runtime error 8 ms 640 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 43 ms 63608 KB Output is correct
2 Correct 40 ms 63608 KB Output is correct
3 Correct 42 ms 63616 KB Output is correct
4 Correct 52 ms 63744 KB Output is correct
5 Correct 48 ms 63736 KB Output is correct
6 Correct 66 ms 63672 KB Output is correct
7 Correct 66 ms 63608 KB Output is correct
8 Correct 120 ms 63864 KB Output is correct
9 Correct 119 ms 64120 KB Output is correct
10 Correct 120 ms 63988 KB Output is correct
11 Correct 163 ms 63872 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 63352 KB Output is correct
2 Correct 39 ms 63360 KB Output is correct
3 Correct 39 ms 63488 KB Output is correct
4 Correct 40 ms 63360 KB Output is correct
5 Correct 40 ms 63480 KB Output is correct
6 Correct 37 ms 63352 KB Output is correct
7 Correct 40 ms 63480 KB Output is correct
8 Correct 42 ms 63352 KB Output is correct
9 Correct 38 ms 63360 KB Output is correct
10 Correct 40 ms 63352 KB Output is correct
11 Correct 37 ms 63352 KB Output is correct
12 Correct 39 ms 63480 KB Output is correct
13 Correct 38 ms 63608 KB Output is correct
14 Correct 38 ms 63480 KB Output is correct
15 Correct 39 ms 63616 KB Output is correct
16 Correct 43 ms 63480 KB Output is correct
17 Correct 40 ms 63608 KB Output is correct
18 Correct 52 ms 63608 KB Output is correct
19 Correct 103 ms 63872 KB Output is correct
20 Correct 105 ms 63996 KB Output is correct
21 Correct 97 ms 63872 KB Output is correct
22 Correct 153 ms 63992 KB Output is correct
23 Runtime error 8 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Halted 0 ms 0 KB -