Submission #134145

#	Time	Username	Problem	Language	Result	Execution time	Memory
134145		AngusRitossa	Abduction 2 (JOI17_abduction2)	C++14	27 / 100	339 ms	126840 KiB

abduction2

#include <bits/stdc++.h>
using namespace std;
int h, w, A[50010], B[50010], q;
int memo[2010][2010][4], done[2010][2010][4];
int dp(int a, int b, int c)
{
	if (a < 0 || b < 0 || a == h || b == w) return -1;
	if (done[a][b][c]) return memo[a][b][c];
	done[a][b][c] = 1;
	if (!c) // going up
	{
		if (B[b] < A[a]) return memo[a][b][c] = max(dp(a, b-1, 2), dp(a, b+1, 3))+1;
		else return memo[a][b][c] = dp(a-1, b, c)+1;
	}
	else if (c == 1)
	{
		if (B[b] < A[a]) return memo[a][b][c] = max(dp(a, b-1, 2), dp(a, b+1, 3))+1;
		else return memo[a][b][c] = dp(a+1, b, c)+1;
	}
	else if (c == 2)
	{
		if (B[b] > A[a]) return memo[a][b][c] = max(dp(a-1, b, 0), dp(a+1, b, 1))+1;
		else return memo[a][b][c] = dp(a, b-1, c)+1;
	}
	else
	{
		if (B[b] > A[a]) return memo[a][b][c] = max(dp(a-1, b, 0), dp(a+1, b, 1))+1;
		else return memo[a][b][c] = dp(a, b+1, c)+1;
	}
}
int main()
{
	scanf("%d%d%d", &h, &w, &q);
	for (int i = 0; i < h; i++) scanf("%d", &A[i]);
	for (int i = 0; i < w; i++) scanf("%d", &B[i]);
	for (int i = 0; i < q; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		a--, b--;
		int ans = max(dp(a-1, b, 0), max(dp(a+1, b, 1), max(dp(a, b-1, 2), dp(a, b+1, 3))))+1;
		printf("%d\n", ans);
	}
}

Compilation message (stderr)

abduction2.cpp: In function 'int main()':
abduction2.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &h, &w, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
abduction2.cpp:34:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < h; i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~
abduction2.cpp:35:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < w; i++) scanf("%d", &B[i]);
                              ~~~~~^~~~~~~~~~~~~
abduction2.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

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