oj.uz

Submission #336758

# Submission time Handle Problem Language Result Execution time Memory
336758 2020-12-16T18:19:14 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
17 / 100
 1679 ms 524292 KB 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <array>
#include <unordered_map>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

typedef array<int, 2> T;

T operator+(T x, T y){
	return {x[0] + y[0], x[1] + y[1]};
}

const int mxn = 50000, k = 4;
const T d[k] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int n[2], q;
int a[2][mxn];
unordered_map<int, int> dp[k][mxn];

int sol(T x, int y){
	for(int i = 0; i < 2; i++) if(x[i] < 0 || x[i] >= n[i]) return 0;
	if(dp[y][x[0]].count(x[1])) return dp[y][x[0]][x[1]];
	int ret = 0;
	if(a[!(y & 1)][x[!(y & 1)]] < a[y & 1][x[y & 1]]){
		for(int i = 0; i < 2; i++){
			int z = (y + 2 * i + 1) % k;
			ret = max(ret, sol(x + d[z], z));
		}
	}else{
		ret = sol(x + d[y], y);
	}
	return dp[y][x[0]][x[1]] = ++ret;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n[0] >> n[1] >> q;
	
	for(int i = 0; i < 2; i++)
	for(int j = 0; j < n[i]; j++){
		cin >> a[i][j];
	}
	
	while(q--){
		T x;
		for(int i = 0; i < 2; i++) cin >> x[i], x[i]--;
		int ret = 0;
		for(int i = 0; i < k; i++) ret = max(ret, sol(x + d[i], i));
		cout << ret << endl;
	}

	return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 8 ms 11244 KB Output is correct
10 Correct 10 ms 11244 KB Output is correct
11 Correct 10 ms 11244 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 8 ms 11244 KB Output is correct
10 Correct 10 ms 11244 KB Output is correct
11 Correct 10 ms 11244 KB Output is correct
12 Correct 10 ms 11756 KB Output is correct
13 Correct 10 ms 11884 KB Output is correct
14 Correct 10 ms 11884 KB Output is correct
15 Correct 10 ms 11884 KB Output is correct
16 Correct 10 ms 11884 KB Output is correct
17 Correct 21 ms 14700 KB Output is correct
18 Correct 91 ms 35308 KB Output is correct
19 Correct 628 ms 245100 KB Output is correct
20 Correct 801 ms 303096 KB Output is correct
21 Correct 717 ms 273004 KB Output is correct
22 Runtime error 715 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 8 ms 11244 KB Output is correct
10 Correct 10 ms 11244 KB Output is correct
11 Correct 10 ms 11244 KB Output is correct
12 Correct 10 ms 11756 KB Output is correct
13 Correct 10 ms 11884 KB Output is correct
14 Correct 10 ms 11884 KB Output is correct
15 Correct 10 ms 11884 KB Output is correct
16 Correct 10 ms 11884 KB Output is correct
17 Correct 21 ms 14700 KB Output is correct
18 Correct 91 ms 35308 KB Output is correct
19 Correct 628 ms 245100 KB Output is correct
20 Correct 801 ms 303096 KB Output is correct
21 Correct 717 ms 273004 KB Output is correct
22 Runtime error 715 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 17004 KB Output is correct
2 Correct 26 ms 16748 KB Output is correct
3 Correct 29 ms 17388 KB Output is correct
4 Correct 29 ms 17388 KB Output is correct
5 Correct 33 ms 17516 KB Output is correct
6 Correct 409 ms 109036 KB Output is correct
7 Correct 402 ms 109512 KB Output is correct
8 Correct 1045 ms 339436 KB Output is correct
9 Correct 1008 ms 350060 KB Output is correct
10 Correct 1016 ms 314860 KB Output is correct
11 Correct 1679 ms 507116 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11244 KB Output is correct
2 Correct 8 ms 11244 KB Output is correct
3 Correct 8 ms 11244 KB Output is correct
4 Correct 8 ms 11244 KB Output is correct
5 Correct 8 ms 11244 KB Output is correct
6 Correct 8 ms 11244 KB Output is correct
7 Correct 8 ms 11244 KB Output is correct
8 Correct 8 ms 11244 KB Output is correct
9 Correct 8 ms 11244 KB Output is correct
10 Correct 10 ms 11244 KB Output is correct
11 Correct 10 ms 11244 KB Output is correct
12 Correct 10 ms 11756 KB Output is correct
13 Correct 10 ms 11884 KB Output is correct
14 Correct 10 ms 11884 KB Output is correct
15 Correct 10 ms 11884 KB Output is correct
16 Correct 10 ms 11884 KB Output is correct
17 Correct 21 ms 14700 KB Output is correct
18 Correct 91 ms 35308 KB Output is correct
19 Correct 628 ms 245100 KB Output is correct
20 Correct 801 ms 303096 KB Output is correct
21 Correct 717 ms 273004 KB Output is correct
22 Runtime error 715 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)