oj.uz

Submission #336777

# Submission time Handle Problem Language Result Execution time Memory
336777 2020-12-16T19:07:51 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 5000 ms 491388 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 = 5;
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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 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 2 ms 748 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 620 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 8 ms 1644 KB Output is correct
18 Correct 38 ms 8464 KB Output is correct
19 Correct 361 ms 144496 KB Output is correct
20 Correct 474 ms 177588 KB Output is correct
21 Correct 407 ms 164272 KB Output is correct
22 Correct 873 ms 462208 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 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 2 ms 748 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 620 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 8 ms 1644 KB Output is correct
18 Correct 38 ms 8464 KB Output is correct
19 Correct 361 ms 144496 KB Output is correct
20 Correct 474 ms 177588 KB Output is correct
21 Correct 407 ms 164272 KB Output is correct
22 Correct 873 ms 462208 KB Output is correct
23 Correct 27 ms 8300 KB Output is correct
24 Correct 36 ms 9964 KB Output is correct
25 Correct 34 ms 11116 KB Output is correct
26 Correct 41 ms 16376 KB Output is correct
27 Correct 26 ms 9708 KB Output is correct
28 Execution timed out 5103 ms 491388 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2412 KB Output is correct
2 Correct 11 ms 2540 KB Output is correct
3 Correct 12 ms 3052 KB Output is correct
4 Correct 14 ms 3308 KB Output is correct
5 Correct 12 ms 2668 KB Output is correct
6 Correct 187 ms 35076 KB Output is correct
7 Correct 188 ms 35624 KB Output is correct
8 Correct 546 ms 177820 KB Output is correct
9 Correct 528 ms 193204 KB Output is correct
10 Correct 513 ms 159916 KB Output is correct
11 Correct 889 ms 275200 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 0 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 2 ms 748 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 620 KB Output is correct
16 Correct 2 ms 748 KB Output is correct
17 Correct 8 ms 1644 KB Output is correct
18 Correct 38 ms 8464 KB Output is correct
19 Correct 361 ms 144496 KB Output is correct
20 Correct 474 ms 177588 KB Output is correct
21 Correct 407 ms 164272 KB Output is correct
22 Correct 873 ms 462208 KB Output is correct
23 Correct 27 ms 8300 KB Output is correct
24 Correct 36 ms 9964 KB Output is correct
25 Correct 34 ms 11116 KB Output is correct
26 Correct 41 ms 16376 KB Output is correct
27 Correct 26 ms 9708 KB Output is correct
28 Execution timed out 5103 ms 491388 KB Time limit exceeded
29 Halted 0 ms 0 KB -