oj.uz

Submission #336769

# Submission time Handle Problem Language Result Execution time Memory
336769 2020-12-16T18:46:39 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
27 / 100
 5000 ms 401132 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 9 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 9 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 10 ms 11500 KB Output is correct
13 Correct 10 ms 11628 KB Output is correct
14 Correct 9 ms 11500 KB Output is correct
15 Correct 10 ms 11628 KB Output is correct
16 Correct 9 ms 11500 KB Output is correct
17 Correct 11 ms 12012 KB Output is correct
18 Correct 30 ms 13932 KB Output is correct
19 Correct 194 ms 102012 KB Output is correct
20 Correct 236 ms 126188 KB Output is correct
21 Correct 212 ms 117740 KB Output is correct
22 Correct 462 ms 335084 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 9 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 10 ms 11500 KB Output is correct
13 Correct 10 ms 11628 KB Output is correct
14 Correct 9 ms 11500 KB Output is correct
15 Correct 10 ms 11628 KB Output is correct
16 Correct 9 ms 11500 KB Output is correct
17 Correct 11 ms 12012 KB Output is correct
18 Correct 30 ms 13932 KB Output is correct
19 Correct 194 ms 102012 KB Output is correct
20 Correct 236 ms 126188 KB Output is correct
21 Correct 212 ms 117740 KB Output is correct
22 Correct 462 ms 335084 KB Output is correct
23 Correct 30 ms 17136 KB Output is correct
24 Correct 37 ms 18924 KB Output is correct
25 Correct 33 ms 18028 KB Output is correct
26 Correct 38 ms 22380 KB Output is correct
27 Correct 28 ms 17900 KB Output is correct
28 Execution timed out 5130 ms 401132 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12396 KB Output is correct
2 Correct 19 ms 12012 KB Output is correct
3 Correct 20 ms 12396 KB Output is correct
4 Correct 20 ms 12524 KB Output is correct
5 Correct 30 ms 12524 KB Output is correct
6 Correct 95 ms 22380 KB Output is correct
7 Correct 90 ms 22252 KB Output is correct
8 Correct 296 ms 120212 KB Output is correct
9 Correct 282 ms 134124 KB Output is correct
10 Correct 269 ms 107116 KB Output is correct
11 Correct 450 ms 176236 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 9 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 10 ms 11500 KB Output is correct
13 Correct 10 ms 11628 KB Output is correct
14 Correct 9 ms 11500 KB Output is correct
15 Correct 10 ms 11628 KB Output is correct
16 Correct 9 ms 11500 KB Output is correct
17 Correct 11 ms 12012 KB Output is correct
18 Correct 30 ms 13932 KB Output is correct
19 Correct 194 ms 102012 KB Output is correct
20 Correct 236 ms 126188 KB Output is correct
21 Correct 212 ms 117740 KB Output is correct
22 Correct 462 ms 335084 KB Output is correct
23 Correct 30 ms 17136 KB Output is correct
24 Correct 37 ms 18924 KB Output is correct
25 Correct 33 ms 18028 KB Output is correct
26 Correct 38 ms 22380 KB Output is correct
27 Correct 28 ms 17900 KB Output is correct
28 Execution timed out 5130 ms 401132 KB Time limit exceeded
29 Halted 0 ms 0 KB -