oj.uz

Submission #336759

# Submission time Handle Problem Language Result Execution time Memory
336759 2020-12-16T18:20:12 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
17 / 100
 1679 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 = 2000, k = 4;
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;
	if(dp[y][x[0]].count(x[1])) return dp[y][x[0]][x[1]];
	int ret = 0;
	if(a[!(y & 1)][x[!(y & 1)]] < a[y & 1][x[y & 1]]){
		for(int i = 0; i < 2; i++){
			int z = (y + 2 * i + 1) % k;
			ret = max(ret, sol(x + d[z], z));
		}
	}else{
		ret = sol(x + d[y], y);
	}
	return dp[y][x[0]][x[1]] = ++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 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 2 ms 1260 KB Output is correct
15 Correct 2 ms 1260 KB Output is correct
16 Correct 2 ms 1388 KB Output is correct
17 Correct 12 ms 4204 KB Output is correct
18 Correct 85 ms 24684 KB Output is correct
19 Correct 643 ms 234400 KB Output is correct
20 Correct 806 ms 292368 KB Output is correct
21 Correct 699 ms 262508 KB Output is correct
22 Runtime error 779 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 2 ms 1260 KB Output is correct
15 Correct 2 ms 1260 KB Output is correct
16 Correct 2 ms 1388 KB Output is correct
17 Correct 12 ms 4204 KB Output is correct
18 Correct 85 ms 24684 KB Output is correct
19 Correct 643 ms 234400 KB Output is correct
20 Correct 806 ms 292368 KB Output is correct
21 Correct 699 ms 262508 KB Output is correct
22 Runtime error 779 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6508 KB Output is correct
2 Correct 20 ms 6252 KB Output is correct
3 Correct 21 ms 6892 KB Output is correct
4 Correct 21 ms 6892 KB Output is correct
5 Correct 21 ms 7020 KB Output is correct
6 Correct 387 ms 98412 KB Output is correct
7 Correct 401 ms 99052 KB Output is correct
8 Correct 1033 ms 328940 KB Output is correct
9 Correct 996 ms 339680 KB Output is correct
10 Correct 983 ms 304620 KB Output is correct
11 Correct 1679 ms 496568 KB Output is correct

Subtask #5
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 748 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 1 ms 748 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1388 KB Output is correct
14 Correct 2 ms 1260 KB Output is correct
15 Correct 2 ms 1260 KB Output is correct
16 Correct 2 ms 1388 KB Output is correct
17 Correct 12 ms 4204 KB Output is correct
18 Correct 85 ms 24684 KB Output is correct
19 Correct 643 ms 234400 KB Output is correct
20 Correct 806 ms 292368 KB Output is correct
21 Correct 699 ms 262508 KB Output is correct
22 Runtime error 779 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)