Submission #647119

#	Time	Username	Problem	Language	Result	Execution time	Memory
647119		messiuuuuu	Abduction 2 (JOI17_abduction2)	C++14	100 / 100	2210 ms	131400 KiB

abduction2

///
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 5e4 + 5;
const ll INF = 1e9 + 5;

int m, n, q;
int a[MAXN], b[MAXN];

void Input()
{
    cin >> m >> n >> q;
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    a[0] = a[m + 1] = b[0] = b[n + 1] = INF;
}

map<int, ll> dp[MAXN][2];

int FindS(int r, int c, bool t)
{
    if (t == 0)
    {
        int i = r - 1;
        for (; a[i] < b[c]; i--);
        return i;
    } else
    {
        int i = c - 1;
        for (; b[i] < a[r]; i--);
        return i;
    }
}

int FindL(int r, int c, bool t)
{
    if (t == 0)
    {
        int i = r + 1;
        for (; a[i] < b[c]; i++);
        return i;
    } else
    {
        int i = c + 1;
        for (; b[i] < a[r]; i++);
        return i;
    }
}

ll DP(int r, int c, bool t)
{
    if (r < 1 || r > m || c < 1 || c > n)
        return -1;
    if (dp[r][t].count(c))
        return dp[r][t][c];
    ll& res = dp[r][t][c];

    int tmp = t == 0 ? r : c;

    int p1 = FindS(r, c, t);
    int d1 = tmp - p1;

    int p2 = FindL(r, c, t);
    int d2 = p2 - tmp;

    res = max(d1 + (t == 0 ? DP(p1, c, !t) : DP(r, p1, !t)), d2 + (t == 0 ? DP(p2, c, !t) : DP(r, p2, !t)));
    return res;
}

void Solve()
{
    while (q-- > 0)
    {
        int s, t;
        cin >> s >> t;
        cout << max(DP(s, t, 0), DP(s, t, 1)) << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".INP","r"))
    {
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    Input();
    Solve();
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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