oj.uz

Submission #332174

# Submission time Handle Problem Language Result Execution time Memory
332174 2020-12-01T15:16:01 Z MahdiBahramian Dango Maker (JOI18_dango_maker) C++11
13 / 100
 1 ms 364 KB 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int Max = 3e3 + 10;

struct V
{
	int i , j , b;
};

int dp[Max];
bool seen[Max][Max][2];
char C[Max][Max];

bool ok(V x)
{
	int i = x.i , j = x.j , v = x.b;
	if(i < 0 || j < 0) return false;
	if(!v) return C[i][j] == 'R' && C[i][j + 1] == 'G' && C[i][j + 2] == 'W';
	else  return C[i][j] == 'R' && C[i + 1][j] == 'G' && C[i + 2][j] == 'W';
}

vector<V> N(V a)
{
	if(a.b)
	{
		vector<V> Ne;
		if(ok(V{a.i , a.j , false})) 
			Ne.pb(V{a.i , a.j , false});
		if(ok(V{a.i + 1 , a.j - 1 , false}))
			Ne.pb(V{a.i + 1, a.j - 1 , false});
		if(ok(V{a.i + 2 , a.j - 2 , false}))
			Ne.pb(V{a.i + 2, a.j - 2 , false});
		return Ne;
	}
	else
	{
		vector<V> Ne;
		if(ok(V{a.i , a.j , true})) 
			Ne.pb(V{a.i , a.j , true});
		if(ok(V{a.i - 1 , a.j + 1 , true}))
			Ne.pb(V{a.i - 1, a.j + 1 , true});
		if(ok(V{a.i - 2 , a.j + 2 , true}))
			Ne.pb(V{a.i - 2, a.j + 2 , true});
		return Ne;
	}
}

void DFS(V v1 , V v2 , int i)
{
	seen[v1.i][v1.j][v1.b] = true;
	if(v2.i >= 0)
		seen[v2.i][v2.j][v2.b] = true;

	vector<V> U;
	vector<V> Ne = N(v1);
	for(V u : Ne) if(!seen[u.i][u.j][u.b]) U.pb(u);
	if(U.size() == 0)
	{
		dp[i] = 1 + int(v2.i >= 0);
		dp[i + 1] = 0;
	}
	else if(U.size() == 1)
	{
		DFS(U[0] , V{-1 , -1 , 0} , i + 1);
		dp[i] = max(dp[i + 1] , dp[i + 2] + 1 + int(v2.i >= 0));

	}
	else if(U.size() == 2)
	{
		DFS(U[0] , U[1] , i + 1);
		dp[i] = max(dp[i + 1] , dp[i + 2] + 1);

	}
}

int n , m;



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n ; i++)
	{
		for(int j = 0; j < m ; j++)
		{
			cin >> C[i][j];
		}
	}
	
	//0 yani ofoghi 
	//1 yani amodi

	int ans = 0;
	for(int i = 0; i < n ; i++)
	{
		for(int j = 0; j < m ; j++)
		{
			for(int b = 0; b < 2; b++)
			{
				if(ok(V{i , j , b}) && !seen[i][j][b])
				{
					vector<V> Ne = N(V{i , j , b});
					if(Ne.size() == 0) ans++;
					else if(Ne.size() == 1)
					{
						DFS(V{i , j , b} , V{-1,-1,0} , 0);
						ans += dp[0];
					}
					else if(Ne.size() == 2 && N(Ne[0]).size() == 2 && N(Ne[1]).size() == 2)
					{
						DFS(V{i , j , b} , V{-1,-1,0} , 0);
						ans += dp[0];
					}
				}
			}
		}
	}

	cout << ans << '\n';
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 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 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 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 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 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 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Incorrect 1 ms 364 KB Output isn't correct
21 Halted 0 ms 0 KB -