Submission #308363

#	Time	Username	Problem	Language	Result	Execution time	Memory
308363		thecodingwizard	Abduction 2 (JOI17_abduction2)	C++11	44 / 100	5028 ms	16660 KiB

abduction2

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

int h, w, q; 
int A[50000], B[50000];

map<pair<int, ii>, int> memo;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int dp(int i, int j, int d) {
    auto memoIdx = mp(i, mp(j, d));
    if (memo.count(memoIdx)) {
        return memo[memoIdx];
    }

    int ans = 0;
    int k = 1;
    while (true) {
        int a = i + dx[d]*k, b = j + dy[d]*k;
        if (a < 0 || a >= h || b < 0 || b >= w) break;
        ans++;
        if ((d == 0 || d == 2) && A[a] > B[j]) {
            ans += max(dp(a, b, 1), dp(a, b, 3));
            break;
        }
        if ((d == 1 || d == 3) && B[b] > A[i]) {
            ans += max(dp(a, b, 0), dp(a, b, 2));
            break;
        }
        k++;
    }

    return memo[memoIdx] = ans;
}

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> h >> w >> q;
    for (int i = 0; i < h; i++) cin >> A[i];
    for (int i = 0; i < w; i++) cin >> B[i];

    for (int i = 0; i < q; i++) {
        int s, t; cin >> s >> t; --s; --t;
        int best = 0;
        for (int j = 0; j < 4; j++) {
            best = max(best, dp(s, t, j));
        }
        cout << best << "\n";
    }

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 10 / 10
• Subtask 3: 17 / 17
• Subtask 4: 4 / 4
• Subtask 5: 0 / 56