oj.uz

Submission #336781

# Submission time Handle Problem Language Result Execution time Memory
336781 2020-12-16T19:11:35 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 4874 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<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] + x[1]) & 1) 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 0 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 0 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 0 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 0 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 1 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 7 ms 2156 KB Output is correct
18 Correct 53 ms 13876 KB Output is correct
19 Correct 388 ms 159156 KB Output is correct
20 Correct 535 ms 211436 KB Output is correct
21 Correct 423 ms 179884 KB Output is correct
22 Correct 925 ms 494328 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 0 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 0 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 1 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 7 ms 2156 KB Output is correct
18 Correct 53 ms 13876 KB Output is correct
19 Correct 388 ms 159156 KB Output is correct
20 Correct 535 ms 211436 KB Output is correct
21 Correct 423 ms 179884 KB Output is correct
22 Correct 925 ms 494328 KB Output is correct
23 Correct 30 ms 9068 KB Output is correct
24 Correct 50 ms 14084 KB Output is correct
25 Correct 38 ms 11908 KB Output is correct
26 Correct 48 ms 19600 KB Output is correct
27 Correct 27 ms 10476 KB Output is correct
28 Runtime error 4874 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 13 ms 3948 KB Output is correct
2 Correct 13 ms 3308 KB Output is correct
3 Correct 13 ms 3692 KB Output is correct
4 Correct 15 ms 3820 KB Output is correct
5 Correct 14 ms 3564 KB Output is correct
6 Correct 230 ms 52996 KB Output is correct
7 Correct 219 ms 45316 KB Output is correct
8 Correct 647 ms 216708 KB Output is correct
9 Correct 636 ms 231808 KB Output is correct
10 Correct 622 ms 198536 KB Output is correct
11 Correct 956 ms 310008 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 0 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 0 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 1 ms 748 KB Output is correct
14 Correct 2 ms 748 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 7 ms 2156 KB Output is correct
18 Correct 53 ms 13876 KB Output is correct
19 Correct 388 ms 159156 KB Output is correct
20 Correct 535 ms 211436 KB Output is correct
21 Correct 423 ms 179884 KB Output is correct
22 Correct 925 ms 494328 KB Output is correct
23 Correct 30 ms 9068 KB Output is correct
24 Correct 50 ms 14084 KB Output is correct
25 Correct 38 ms 11908 KB Output is correct
26 Correct 48 ms 19600 KB Output is correct
27 Correct 27 ms 10476 KB Output is correct
28 Runtime error 4874 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -