oj.uz

Submission #336764

# Submission time Handle Problem Language Result Execution time Memory
336764 2020-12-16T18:42:35 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 5000 ms 394724 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, w = 10;
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;
	int ret = 0;
	if(dp[y][x[0]].count(x[1])){
		ret = dp[y][x[0]][x[1]];
	}else if(a[!(y & 1)][x[!(y & 1)]] > a[y & 1][x[y & 1]]){
		ret = sol(x + d[y], y);
		if(!(x[0] % w) || !(x[1] % w)) dp[y][x[0]][x[1]] = ret;
	}else{
		for(int i = 0; i < 2; i++){
			int z = (y + 2 * i + 1) % k;
			ret = max(ret, sol(x + d[z], z));
		}
		dp[y][x[0]][x[1]] = ret;
	}
	return ++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 9 ms 11264 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct

Subtask #2
10.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 9 ms 11264 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 11 ms 11648 KB Output is correct
13 Correct 9 ms 11628 KB Output is correct
14 Correct 9 ms 11500 KB Output is correct
15 Correct 9 ms 11628 KB Output is correct
16 Correct 9 ms 11628 KB Output is correct
17 Correct 12 ms 12140 KB Output is correct
18 Correct 33 ms 15724 KB Output is correct
19 Correct 235 ms 114284 KB Output is correct
20 Correct 298 ms 140524 KB Output is correct
21 Correct 261 ms 130156 KB Output is correct
22 Correct 577 ms 358708 KB Output is correct

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 9 ms 11264 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 11 ms 11648 KB Output is correct
13 Correct 9 ms 11628 KB Output is correct
14 Correct 9 ms 11500 KB Output is correct
15 Correct 9 ms 11628 KB Output is correct
16 Correct 9 ms 11628 KB Output is correct
17 Correct 12 ms 12140 KB Output is correct
18 Correct 33 ms 15724 KB Output is correct
19 Correct 235 ms 114284 KB Output is correct
20 Correct 298 ms 140524 KB Output is correct
21 Correct 261 ms 130156 KB Output is correct
22 Correct 577 ms 358708 KB Output is correct
23 Correct 33 ms 18284 KB Output is correct
24 Correct 49 ms 18412 KB Output is correct
25 Correct 34 ms 19072 KB Output is correct
26 Correct 42 ms 24428 KB Output is correct
27 Correct 33 ms 19564 KB Output is correct
28 Execution timed out 5053 ms 394724 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12652 KB Output is correct
2 Correct 16 ms 12652 KB Output is correct
3 Correct 17 ms 12908 KB Output is correct
4 Correct 17 ms 12908 KB Output is correct
5 Correct 16 ms 12652 KB Output is correct
6 Correct 118 ms 29420 KB Output is correct
7 Correct 124 ms 29804 KB Output is correct
8 Correct 369 ms 137728 KB Output is correct
9 Correct 357 ms 152428 KB Output is correct
10 Correct 349 ms 125676 KB Output is correct
11 Correct 593 ms 202604 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 9 ms 11264 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 11 ms 11648 KB Output is correct
13 Correct 9 ms 11628 KB Output is correct
14 Correct 9 ms 11500 KB Output is correct
15 Correct 9 ms 11628 KB Output is correct
16 Correct 9 ms 11628 KB Output is correct
17 Correct 12 ms 12140 KB Output is correct
18 Correct 33 ms 15724 KB Output is correct
19 Correct 235 ms 114284 KB Output is correct
20 Correct 298 ms 140524 KB Output is correct
21 Correct 261 ms 130156 KB Output is correct
22 Correct 577 ms 358708 KB Output is correct
23 Correct 33 ms 18284 KB Output is correct
24 Correct 49 ms 18412 KB Output is correct
25 Correct 34 ms 19072 KB Output is correct
26 Correct 42 ms 24428 KB Output is correct
27 Correct 33 ms 19564 KB Output is correct
28 Execution timed out 5053 ms 394724 KB Time limit exceeded
29 Halted 0 ms 0 KB -