oj.uz

답안 #891744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
891744 2023-12-23T22:33:45 Z Hakiers Dango Maker (JOI18_dango_maker) C++17
33 / 100
 3 ms 4956 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 3e3 + 7;
char tab[MAXN][MAXN];
vector<pair<int, int>> diagonal[MAXN<<1][2]; //horizontal 0, vertical 1
int res;
int n, m;

void checkHorizontal(int y, int x, int id){
	if(tab[y][x] != 'R') return;
	else if(tab[y][x+1] != 'G') return;
	else if(tab[y][x+2] != 'W') return;
	int act = 1;
	
	//cout << "y " << y << " x " << x << "\n";
	
	if(diagonal[id][0].size())
		act = max(act, diagonal[id][0].back().second + 1);
	if(diagonal[id][1].size())
		act = max(act, diagonal[id][1].back().second + 1);
	
	diagonal[id][0].push_back({x, act});
}

void checkVertical(int y, int x, int id){
	if(tab[y][x] != 'R') return;
	else if(tab[y+1][x] != 'G') return;
	else if(tab[y+2][x] != 'W') return;
	int act = 1;
	
	//cout << "y " << y << " x " << x << "\n";
	
	if(diagonal[id][1].size())
		act = max(act, diagonal[id][1].back().second + 1);
	
	int it = int(diagonal[id][0].size())-1;
	
	while(it >= 0){
		if(diagonal[id][0][it].first + 3 <= x){
			act = max(act, diagonal[id][0][it].second + 1);
			break;
		}
		it--;
	}
	
	diagonal[id][1].push_back({x, act});
}

void addres(int id){
	int best = 0;
	if(diagonal[id][0].size())
		best = max(best, diagonal[id][0].back().second);
	if(diagonal[id][1].size())
		best = max(best, diagonal[id][1].back().second);
	res += best;
}

void solve(){
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; 0 <= (i-j); j++){
			if(j + 2 <= m)
				checkHorizontal((i-j+1), j, i);
			if((i-j+1)+2 <= n) 
				checkVertical((i-j+1), j, i);
		}
		addres(i);
	}
	
	
	
	for(int j = 2; j <= m; j++){
		for(int i = n; (n-i) + j <= m ; i--){
			if((n-i) + j + 2 <= m)
				checkHorizontal(i, (n-i) + j, n+j);
			if(i+2 <= n) 
				checkVertical(i, (n-i) + j, n+j);
		}
		addres(n+j);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= m; j++)
			cin >> tab[i][j];
			
	solve();
	cout << res << "\n";
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2700 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2700 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2696 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Correct 1 ms 2652 KB Output is correct
30 Correct 1 ms 2648 KB Output is correct
31 Correct 1 ms 2652 KB Output is correct
32 Correct 2 ms 2652 KB Output is correct
33 Correct 1 ms 2648 KB Output is correct
34 Correct 1 ms 2652 KB Output is correct
35 Correct 1 ms 2652 KB Output is correct
36 Correct 1 ms 2652 KB Output is correct
37 Correct 1 ms 2648 KB Output is correct
38 Correct 1 ms 2652 KB Output is correct
39 Correct 1 ms 2652 KB Output is correct
40 Correct 1 ms 2652 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 1 ms 2652 KB Output is correct
43 Correct 1 ms 2648 KB Output is correct
44 Correct 1 ms 2652 KB Output is correct
45 Correct 1 ms 2652 KB Output is correct
46 Correct 1 ms 2652 KB Output is correct
47 Correct 1 ms 2652 KB Output is correct
48 Correct 1 ms 2652 KB Output is correct
49 Correct 1 ms 2652 KB Output is correct
50 Correct 1 ms 2648 KB Output is correct
51 Correct 1 ms 2804 KB Output is correct
52 Correct 1 ms 2692 KB Output is correct
53 Correct 1 ms 2696 KB Output is correct

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2700 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2648 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2648 KB Output is correct
15 Correct 1 ms 2648 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2696 KB Output is correct
18 Correct 1 ms 2652 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 1 ms 2652 KB Output is correct
24 Correct 1 ms 2652 KB Output is correct
25 Correct 1 ms 2652 KB Output is correct
26 Correct 1 ms 2652 KB Output is correct
27 Correct 1 ms 2652 KB Output is correct
28 Correct 1 ms 2652 KB Output is correct
29 Correct 1 ms 2652 KB Output is correct
30 Correct 1 ms 2648 KB Output is correct
31 Correct 1 ms 2652 KB Output is correct
32 Correct 2 ms 2652 KB Output is correct
33 Correct 1 ms 2648 KB Output is correct
34 Correct 1 ms 2652 KB Output is correct
35 Correct 1 ms 2652 KB Output is correct
36 Correct 1 ms 2652 KB Output is correct
37 Correct 1 ms 2648 KB Output is correct
38 Correct 1 ms 2652 KB Output is correct
39 Correct 1 ms 2652 KB Output is correct
40 Correct 1 ms 2652 KB Output is correct
41 Correct 1 ms 2652 KB Output is correct
42 Correct 1 ms 2652 KB Output is correct
43 Correct 1 ms 2648 KB Output is correct
44 Correct 1 ms 2652 KB Output is correct
45 Correct 1 ms 2652 KB Output is correct
46 Correct 1 ms 2652 KB Output is correct
47 Correct 1 ms 2652 KB Output is correct
48 Correct 1 ms 2652 KB Output is correct
49 Correct 1 ms 2652 KB Output is correct
50 Correct 1 ms 2648 KB Output is correct
51 Correct 1 ms 2804 KB Output is correct
52 Correct 1 ms 2692 KB Output is correct
53 Correct 1 ms 2696 KB Output is correct
54 Runtime error 3 ms 4956 KB Execution killed with signal 11
55 Halted 0 ms 0 KB -