Submission #891744

#	Time	Username	Problem	Language	Result	Execution time	Memory
891744		Hakiers	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	3 ms	4956 KiB

dango_maker

#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 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67