oj.uz

Submission #336757

# Submission time Handle Problem Language Result Execution time Memory
336757 2020-12-16T18:18:25 Z super_j6 Abduction 2 (JOI17_abduction2) C++14
17 / 100
 1683 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;
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){
	if(dp[y][x[0]].count(x[1])) return dp[y][x[0]][x[1]];
	for(int i = 0; i < 2; i++) if(x[i] < 0 || x[i] >= n[i]) return 0;
	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 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 9 ms 11244 KB Output is correct
5 Correct 10 ms 11372 KB Output is correct
6 Correct 10 ms 11244 KB Output is correct
7 Correct 9 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 11264 KB Output is correct
11 Correct 9 ms 11244 KB Output is correct

Subtask #2
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 9 ms 11244 KB Output is correct
5 Correct 10 ms 11372 KB Output is correct
6 Correct 10 ms 11244 KB Output is correct
7 Correct 9 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 11264 KB Output is correct
11 Correct 9 ms 11244 KB Output is correct
12 Correct 10 ms 11756 KB Output is correct
13 Correct 10 ms 11884 KB Output is correct
14 Correct 10 ms 11884 KB Output is correct
15 Correct 10 ms 11884 KB Output is correct
16 Correct 10 ms 11884 KB Output is correct
17 Correct 20 ms 14700 KB Output is correct
18 Correct 91 ms 35180 KB Output is correct
19 Correct 645 ms 244992 KB Output is correct
20 Correct 789 ms 302956 KB Output is correct
21 Correct 687 ms 273132 KB Output is correct
22 Runtime error 797 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 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 9 ms 11244 KB Output is correct
5 Correct 10 ms 11372 KB Output is correct
6 Correct 10 ms 11244 KB Output is correct
7 Correct 9 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 11264 KB Output is correct
11 Correct 9 ms 11244 KB Output is correct
12 Correct 10 ms 11756 KB Output is correct
13 Correct 10 ms 11884 KB Output is correct
14 Correct 10 ms 11884 KB Output is correct
15 Correct 10 ms 11884 KB Output is correct
16 Correct 10 ms 11884 KB Output is correct
17 Correct 20 ms 14700 KB Output is correct
18 Correct 91 ms 35180 KB Output is correct
19 Correct 645 ms 244992 KB Output is correct
20 Correct 789 ms 302956 KB Output is correct
21 Correct 687 ms 273132 KB Output is correct
22 Runtime error 797 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 28 ms 17132 KB Output is correct
2 Correct 27 ms 16768 KB Output is correct
3 Correct 30 ms 17528 KB Output is correct
4 Correct 29 ms 17388 KB Output is correct
5 Correct 32 ms 17644 KB Output is correct
6 Correct 411 ms 109036 KB Output is correct
7 Correct 417 ms 109568 KB Output is correct
8 Correct 1042 ms 339436 KB Output is correct
9 Correct 1010 ms 350188 KB Output is correct
10 Correct 995 ms 315244 KB Output is correct
11 Correct 1683 ms 507280 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 9 ms 11244 KB Output is correct
5 Correct 10 ms 11372 KB Output is correct
6 Correct 10 ms 11244 KB Output is correct
7 Correct 9 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 11264 KB Output is correct
11 Correct 9 ms 11244 KB Output is correct
12 Correct 10 ms 11756 KB Output is correct
13 Correct 10 ms 11884 KB Output is correct
14 Correct 10 ms 11884 KB Output is correct
15 Correct 10 ms 11884 KB Output is correct
16 Correct 10 ms 11884 KB Output is correct
17 Correct 20 ms 14700 KB Output is correct
18 Correct 91 ms 35180 KB Output is correct
19 Correct 645 ms 244992 KB Output is correct
20 Correct 789 ms 302956 KB Output is correct
21 Correct 687 ms 273132 KB Output is correct
22 Runtime error 797 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)