oj.uz

Submission #336767

# Submission time Handle Problem Language Result Execution time Memory
336767 2020-12-16T18:44:17 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 4333 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, w = 3;
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 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 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 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 9 ms 11500 KB Output is correct
13 Correct 10 ms 12012 KB Output is correct
14 Correct 10 ms 11752 KB Output is correct
15 Correct 10 ms 11756 KB Output is correct
16 Correct 10 ms 11756 KB Output is correct
17 Correct 16 ms 13420 KB Output is correct
18 Correct 61 ms 24044 KB Output is correct
19 Correct 441 ms 165100 KB Output is correct
20 Correct 581 ms 206316 KB Output is correct
21 Correct 505 ms 187884 KB Output is correct
22 Correct 1082 ms 474860 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 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 9 ms 11500 KB Output is correct
13 Correct 10 ms 12012 KB Output is correct
14 Correct 10 ms 11752 KB Output is correct
15 Correct 10 ms 11756 KB Output is correct
16 Correct 10 ms 11756 KB Output is correct
17 Correct 16 ms 13420 KB Output is correct
18 Correct 61 ms 24044 KB Output is correct
19 Correct 441 ms 165100 KB Output is correct
20 Correct 581 ms 206316 KB Output is correct
21 Correct 505 ms 187884 KB Output is correct
22 Correct 1082 ms 474860 KB Output is correct
23 Correct 39 ms 20332 KB Output is correct
24 Correct 57 ms 25964 KB Output is correct
25 Correct 43 ms 22648 KB Output is correct
26 Correct 65 ms 28140 KB Output is correct
27 Correct 36 ms 20844 KB Output is correct
28 Runtime error 4333 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14720 KB Output is correct
2 Correct 20 ms 14060 KB Output is correct
3 Correct 23 ms 14828 KB Output is correct
4 Correct 23 ms 14956 KB Output is correct
5 Correct 23 ms 15084 KB Output is correct
6 Correct 273 ms 65260 KB Output is correct
7 Correct 266 ms 65004 KB Output is correct
8 Correct 731 ms 220856 KB Output is correct
9 Correct 686 ms 231276 KB Output is correct
10 Correct 682 ms 202732 KB Output is correct
11 Correct 1160 ms 328532 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 8 ms 11244 KB Output is correct
11 Correct 8 ms 11244 KB Output is correct
12 Correct 9 ms 11500 KB Output is correct
13 Correct 10 ms 12012 KB Output is correct
14 Correct 10 ms 11752 KB Output is correct
15 Correct 10 ms 11756 KB Output is correct
16 Correct 10 ms 11756 KB Output is correct
17 Correct 16 ms 13420 KB Output is correct
18 Correct 61 ms 24044 KB Output is correct
19 Correct 441 ms 165100 KB Output is correct
20 Correct 581 ms 206316 KB Output is correct
21 Correct 505 ms 187884 KB Output is correct
22 Correct 1082 ms 474860 KB Output is correct
23 Correct 39 ms 20332 KB Output is correct
24 Correct 57 ms 25964 KB Output is correct
25 Correct 43 ms 22648 KB Output is correct
26 Correct 65 ms 28140 KB Output is correct
27 Correct 36 ms 20844 KB Output is correct
28 Runtime error 4333 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -