oj.uz

Submission #748364

# Submission time Handle Problem Language Result Execution time Memory
748364 2023-05-26T07:41:09 Z GrindMachine Abduction 2 (JOI17_abduction2) C++17
23 / 100
 5000 ms 256176 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi

*/

const int MOD = 1e9 + 7;
const int N = 2e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

ll n,m,q;
vector<ll> a(N), b(N);
ll dp[N][N][4];

ll go(ll i, ll j, ll d){
    if(i < 1 or i > n or j < 1 or j > m) return -inf1;
    if(dp[i][j][d] != -1) return dp[i][j][d];

    ll ans = 0;

    if(d <= 1){
        if(b[j] > a[i]){
            amax(ans, 1 + go(i-1,j,2));
            amax(ans, 1 + go(i+1,j,3));
        }
        else{
            if(d == 0){
                amax(ans, 1 + go(i,j-1,d));
            }
            else{
                amax(ans, 1 + go(i,j+1,d));
            }
        }
    }
    else{
        if(a[i] > b[j]){
            amax(ans, 1 + go(i,j-1,0));
            amax(ans, 1 + go(i,j+1,1));       
        }
        else{
            if(d == 2){
                amax(ans, 1 + go(i-1,j,d));
            }
            else{
                amax(ans, 1 + go(i+1,j,d));
            }
        }
    }

    return dp[i][j][d] = ans;
}

void solve(int test_case)
{
    cin >> n >> m >> q;
    rep1(i,n) cin >> a[i];
    rep1(i,m) cin >> b[i];

    while(q--){
        ll i,j; cin >> i >> j;
        memset(dp,-1,sizeof dp);
        ll ans = 1 + max({go(i,j-1,0), go(i,j+1,1), go(i-1,j,2), go(i+1,j,3)});
        cout << ans << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 126156 KB Output is correct
2 Correct 54 ms 126200 KB Output is correct
3 Correct 54 ms 126168 KB Output is correct
4 Correct 49 ms 126208 KB Output is correct
5 Correct 48 ms 126156 KB Output is correct
6 Correct 50 ms 126244 KB Output is correct
7 Correct 56 ms 126196 KB Output is correct
8 Correct 52 ms 126220 KB Output is correct
9 Correct 54 ms 126156 KB Output is correct
10 Correct 49 ms 126100 KB Output is correct
11 Correct 49 ms 126132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 126156 KB Output is correct
2 Correct 54 ms 126200 KB Output is correct
3 Correct 54 ms 126168 KB Output is correct
4 Correct 49 ms 126208 KB Output is correct
5 Correct 48 ms 126156 KB Output is correct
6 Correct 50 ms 126244 KB Output is correct
7 Correct 56 ms 126196 KB Output is correct
8 Correct 52 ms 126220 KB Output is correct
9 Correct 54 ms 126156 KB Output is correct
10 Correct 49 ms 126100 KB Output is correct
11 Correct 49 ms 126132 KB Output is correct
12 Correct 49 ms 126224 KB Output is correct
13 Correct 51 ms 126284 KB Output is correct
14 Correct 51 ms 126264 KB Output is correct
15 Correct 51 ms 126292 KB Output is correct
16 Correct 50 ms 126276 KB Output is correct
17 Correct 51 ms 126280 KB Output is correct
18 Correct 58 ms 126356 KB Output is correct
19 Correct 107 ms 126756 KB Output is correct
20 Correct 122 ms 126676 KB Output is correct
21 Correct 112 ms 126700 KB Output is correct
22 Correct 164 ms 126704 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 126156 KB Output is correct
2 Correct 54 ms 126200 KB Output is correct
3 Correct 54 ms 126168 KB Output is correct
4 Correct 49 ms 126208 KB Output is correct
5 Correct 48 ms 126156 KB Output is correct
6 Correct 50 ms 126244 KB Output is correct
7 Correct 56 ms 126196 KB Output is correct
8 Correct 52 ms 126220 KB Output is correct
9 Correct 54 ms 126156 KB Output is correct
10 Correct 49 ms 126100 KB Output is correct
11 Correct 49 ms 126132 KB Output is correct
12 Correct 49 ms 126224 KB Output is correct
13 Correct 51 ms 126284 KB Output is correct
14 Correct 51 ms 126264 KB Output is correct
15 Correct 51 ms 126292 KB Output is correct
16 Correct 50 ms 126276 KB Output is correct
17 Correct 51 ms 126280 KB Output is correct
18 Correct 58 ms 126356 KB Output is correct
19 Correct 107 ms 126756 KB Output is correct
20 Correct 122 ms 126676 KB Output is correct
21 Correct 112 ms 126700 KB Output is correct
22 Correct 164 ms 126704 KB Output is correct
23 Runtime error 155 ms 256176 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1398 ms 126460 KB Output is correct
2 Correct 1397 ms 126428 KB Output is correct
3 Correct 1410 ms 126436 KB Output is correct
4 Correct 1344 ms 126424 KB Output is correct
5 Correct 1370 ms 126448 KB Output is correct
6 Correct 3032 ms 126508 KB Output is correct
7 Correct 2851 ms 126692 KB Output is correct
8 Execution timed out 5033 ms 126884 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 126156 KB Output is correct
2 Correct 54 ms 126200 KB Output is correct
3 Correct 54 ms 126168 KB Output is correct
4 Correct 49 ms 126208 KB Output is correct
5 Correct 48 ms 126156 KB Output is correct
6 Correct 50 ms 126244 KB Output is correct
7 Correct 56 ms 126196 KB Output is correct
8 Correct 52 ms 126220 KB Output is correct
9 Correct 54 ms 126156 KB Output is correct
10 Correct 49 ms 126100 KB Output is correct
11 Correct 49 ms 126132 KB Output is correct
12 Correct 49 ms 126224 KB Output is correct
13 Correct 51 ms 126284 KB Output is correct
14 Correct 51 ms 126264 KB Output is correct
15 Correct 51 ms 126292 KB Output is correct
16 Correct 50 ms 126276 KB Output is correct
17 Correct 51 ms 126280 KB Output is correct
18 Correct 58 ms 126356 KB Output is correct
19 Correct 107 ms 126756 KB Output is correct
20 Correct 122 ms 126676 KB Output is correct
21 Correct 112 ms 126700 KB Output is correct
22 Correct 164 ms 126704 KB Output is correct
23 Runtime error 155 ms 256176 KB Execution killed with signal 6
24 Halted 0 ms 0 KB -