Submission #234925

#	Time	Username	Problem	Language	Result	Execution time	Memory
234925		amoo_safar	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	250 ms	68728 KiB

dango_maker

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 3e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll n, m;
str s[N];

int Right(int i, int j){
	if(j + 2 >= m) return false;
	return (s[i][j] == 'R') && (s[i][j + 1] == 'G') && (s[i][j + 2] == 'W');
}

int Down(int i, int j){
	if(i + 2 >= n) return false;
	return (s[i][j] == 'R') && (s[i + 1][j] == 'G') && (s[i + 2][j] == 'W');
}

vector<int> V[N + N];

int dp[N][4];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> s[i];
	for(int i = 0; i < n + m - 1; i++) V[i].pb(0);
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			V[i + j].pb(Right(i, j) * 2 + Down(i, j));
		}
	}
	ll ans = 0;
	int k;
	for(int i = 0; i < n + m - 1; i++){
		k = V[i].size();
		for(int i = 0; i < k; i++) fill(dp[i], dp[i] + 4, -Inf);
		dp[0][0] = 0;
		for(int j = 1; j < k; j++){
			for(int mk = 0; mk < 4; mk++){
				dp[j][(mk << 1) & 3] = max(dp[j][(mk << 1) & 3], dp[j - 1][mk]);
			}
			if(V[i][j] & 1){
				for(int mk = 0; mk < 4; mk++){
					dp[j][(mk << 1 | 1 ) & 3] = max(dp[j][(mk << 1 | 1 ) & 3], dp[j - 1][mk] + 1);
				}
			}
			if(V[i][j] & 2){
				dp[j][0] = max(dp[j][0], dp[j - 1][0] + 1);
			}
		}
		ans += *max_element(dp[k - 1], dp[k - 1] + 4);
	}
	cout << ans << '\n';
	return 0;
}

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