Submission #103224

#	Time	Username	Problem	Language	Result	Execution time	Memory
103224		Alisabzi	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	223 ms	19064 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
#define F first 
#define S second
const ll N = 3033 ;
int n, m, ans, dp[N][3];
string s[N] ;
int main()
{ 
	ios::sync_with_stdio(false);cin.tie();cout.tie();
	cin >> n >> m ;
	for(int i = 0 ; i < n ; i ++)
		cin >> s[i] ;
	for(int i = 0 ; i < n+m-2 ; i ++){
		int now = 0 ; 
		int a1 = min(n-1, i), a2 = i-a1 ;
		dp[a2][0] = 0 ;
		dp[a2][1] = (a2 > 0 and s[a1][a2-1] == 'R' and s[a1][a2] == 'G' and s[a1][a2+1] == 'W') ;
		dp[a2][2] = (a1 > 0 and s[a1-1][a2] == 'R' and s[a1][a2] == 'G' and s[a1+1][a2] == 'W') ;
		now = max(dp[a2][1], dp[a2][2]) ;
		for(int x = min(n-1, i)-1 ; x >= 0 ; x --){
			int y = i-x ; if(y < 0 or y >= m) break ;
			dp[y][0] = max(dp[y-1][0], max(dp[y-1][1], dp[y-1][2])) ;
			dp[y][1] = 0 ; 
			if(y > 0 and s[x][y-1] == 'R' and s[x][y] == 'G' and s[x][y+1] == 'W')
				dp[y][1] = max(dp[y-1][1], dp[y-1][0]) + 1 ;
			dp[y][2] = 0 ; 
			if(x > 0 and s[x-1][y] == 'R' and s[x][y] == 'G' and s[x+1][y] == 'W')
				dp[y][2] = max(dp[y-1][2], dp[y-1][0]) + 1 ;
			now = max(dp[y][0], max(dp[y][1], dp[y][2])) ;
		}
		ans += now ;
	}
	cout << ans ;
} 

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