Submission #717972

#	Time	Username	Problem	Language	Result	Execution time	Memory
717972		YeoBL	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	289 ms	35668 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n, m, tmp, tot = 0; cin >> n >> m;
	char ch[n][m];
	bool h[n][m], v[n][m];
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			h[i][j] = v[i][j] = 0;
			cin >> ch[i][j];
		}
	}
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (ch[i][j] != 'G') continue;
			if (i != 0 and i != n - 1 and ch[i - 1][j] == 'R' and ch[i + 1][j] == 'W') v[i][j] = 1;
			if (j != 0 and j != m - 1 and ch[i][j - 1] == 'R' and ch[i][j + 1] == 'W') h[i][j] = 1;
		}
	}
	/*for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cerr << v[i][j];
		}
		cerr << '\n';
	}
	cerr << "HORI\n";
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cerr << h[i][j];
		}
		cerr << '\n';
	}*/
	for (int diag = 0; diag < n + m - 1; diag++){
		int dp[n][2]; tmp = 0;
		bool flag = 0;
		for (int x = 0; x < n; x++){
			int y = diag - x;
			if (y < 0) break;
			if (y >= m) continue;
			if (flag){
				dp[x][0] = max(dp[x - 1][1], dp[x - 1][0] + h[x][y]);
				dp[x][1] = max(dp[x - 1][1] + v[x][y], dp[x - 1][0]);
			}
			else{
				if (h[x][y]) dp[x][0] = 1;
				else dp[x][0] = 0;
				if (v[x][y]) dp[x][1] = 1;
				else dp[x][1] = 0;
			}
			flag = 1;
			//if (diag == 6) cerr << "BOTH: " << dp[x][0] << ' ' << dp[x][1] << '\n';
			tmp = max(tmp, max(dp[x][0], dp[x][1]));
		}
		//cerr << diag << ' ' << tmp << '\n';
		tot += tmp;
	}
	cout << tot;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67