oj.uz

Submission #336778

# Submission time Handle Problem Language Result Execution time Memory
336778 2020-12-16T19:08:29 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 4799 ms 524296 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 = 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] % w) || !(x[1] % w)) 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 1 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 1 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 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 6 ms 1772 KB Output is correct
18 Correct 40 ms 9616 KB Output is correct
19 Correct 378 ms 153132 KB Output is correct
20 Correct 475 ms 187924 KB Output is correct
21 Correct 412 ms 171848 KB Output is correct
22 Correct 924 ms 480000 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 6 ms 1772 KB Output is correct
18 Correct 40 ms 9616 KB Output is correct
19 Correct 378 ms 153132 KB Output is correct
20 Correct 475 ms 187924 KB Output is correct
21 Correct 412 ms 171848 KB Output is correct
22 Correct 924 ms 480000 KB Output is correct
23 Correct 34 ms 10756 KB Output is correct
24 Correct 44 ms 12804 KB Output is correct
25 Correct 31 ms 10220 KB Output is correct
26 Correct 48 ms 19448 KB Output is correct
27 Correct 30 ms 11512 KB Output is correct
28 Runtime error 4799 ms 524296 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 11 ms 2540 KB Output is correct
2 Correct 11 ms 2796 KB Output is correct
3 Correct 13 ms 3308 KB Output is correct
4 Correct 13 ms 3436 KB Output is correct
5 Correct 13 ms 3180 KB Output is correct
6 Correct 200 ms 40324 KB Output is correct
7 Correct 205 ms 40452 KB Output is correct
8 Correct 628 ms 206724 KB Output is correct
9 Correct 613 ms 222712 KB Output is correct
10 Correct 602 ms 191604 KB Output is correct
11 Correct 948 ms 294528 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 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 1 ms 364 KB Output is correct
10 Correct 0 ms 364 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 748 KB Output is correct
13 Correct 2 ms 748 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 748 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 6 ms 1772 KB Output is correct
18 Correct 40 ms 9616 KB Output is correct
19 Correct 378 ms 153132 KB Output is correct
20 Correct 475 ms 187924 KB Output is correct
21 Correct 412 ms 171848 KB Output is correct
22 Correct 924 ms 480000 KB Output is correct
23 Correct 34 ms 10756 KB Output is correct
24 Correct 44 ms 12804 KB Output is correct
25 Correct 31 ms 10220 KB Output is correct
26 Correct 48 ms 19448 KB Output is correct
27 Correct 30 ms 11512 KB Output is correct
28 Runtime error 4799 ms 524296 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -