oj.uz

Submission #336776

# Submission time Handle Problem Language Result Execution time Memory
336776 2020-12-16T19:07:14 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 4255 ms 524288 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<ll, int> dp[k];
 
int sol(T x, int y){
	for(int i = 0; i < 2; i++) if(x[i] < 0 || x[i] >= n[i]) return 0;
	ll f = (ll)x[0] * mxn + x[1];
	int ret = 0;
	if(dp[y].count(f)){
		ret = dp[y][f];
	} else if(a[!(y & 1)][x[!(y & 1)]] > a[y & 1][x[y & 1]]){
		ret = sol(x + d[y], y);
		if(!(x[0] % 3) || !(x[1] % 3)) dp[y][f] = 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][f] = 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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 8 ms 2432 KB Output is correct
18 Correct 55 ms 14004 KB Output is correct
19 Correct 405 ms 164656 KB Output is correct
20 Correct 566 ms 220936 KB Output is correct
21 Correct 478 ms 197964 KB Output is correct
22 Correct 968 ms 507276 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 8 ms 2432 KB Output is correct
18 Correct 55 ms 14004 KB Output is correct
19 Correct 405 ms 164656 KB Output is correct
20 Correct 566 ms 220936 KB Output is correct
21 Correct 478 ms 197964 KB Output is correct
22 Correct 968 ms 507276 KB Output is correct
23 Correct 32 ms 9848 KB Output is correct
24 Correct 51 ms 15376 KB Output is correct
25 Correct 36 ms 12280 KB Output is correct
26 Correct 46 ms 18040 KB Output is correct
27 Correct 28 ms 10220 KB Output is correct
28 Runtime error 4255 ms 524288 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 14 ms 3820 KB Output is correct
2 Correct 12 ms 2924 KB Output is correct
3 Correct 15 ms 3692 KB Output is correct
4 Correct 14 ms 4076 KB Output is correct
5 Correct 15 ms 4076 KB Output is correct
6 Correct 265 ms 57240 KB Output is correct
7 Correct 262 ms 57016 KB Output is correct
8 Correct 669 ms 225836 KB Output is correct
9 Correct 652 ms 240508 KB Output is correct
10 Correct 642 ms 207232 KB Output is correct
11 Correct 1150 ms 360108 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 0 ms 364 KB Output is correct
9 Correct 0 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 2 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 8 ms 2432 KB Output is correct
18 Correct 55 ms 14004 KB Output is correct
19 Correct 405 ms 164656 KB Output is correct
20 Correct 566 ms 220936 KB Output is correct
21 Correct 478 ms 197964 KB Output is correct
22 Correct 968 ms 507276 KB Output is correct
23 Correct 32 ms 9848 KB Output is correct
24 Correct 51 ms 15376 KB Output is correct
25 Correct 36 ms 12280 KB Output is correct
26 Correct 46 ms 18040 KB Output is correct
27 Correct 28 ms 10220 KB Output is correct
28 Runtime error 4255 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -