Submission #962463

#	Time	Username	Problem	Language	Result	Execution time	Memory
962463		LCJLY	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	209 ms	160268 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
typedef pair<int,pii>pi2;

int n,m;
string arr[3005];
int dp[3005][3005]; //horizontal 
int dp2[3005][3005]; //vertical

bool f(int a, int b){
	//hori
	if(b+1>=m||b-1<0) return false;
	return (arr[a][b-1]=='R'&&arr[a][b]=='G'&&arr[a][b+1]=='W');
}

bool f2(int a, int b){
	if(a+1>=n||a-1<0) return false;
	return (arr[a-1][b]=='R'&&arr[a][b]=='G'&&arr[a+1][b]=='W');
}

void solve(){
	cin >> n >> m;
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	for(int x=0;x<n;x++){
		for(int y=m-1;y>=0;y--){
			if(x>0){
				//notake
				int maxi=max(dp[x-1][y+1],dp2[x-1][y+1]);
				dp[x][y]=maxi;
				dp2[x][y]=maxi;
			}
			if(f(x,y)){
				//take horizontal
				if(x==0) dp[x][y]=1;
				else{
					dp[x][y]=max(dp[x-1][y+1]+1,dp[x][y]);
				}
			}	
			
			if(f2(x,y)){
				//take vertical
				if(x==0) dp2[x][y]=1;
				else{
					dp2[x][y]=max(dp2[x-1][y+1]+1,dp2[x][y]);
				}
			}
			
			//show2(dp[x][y],dp[x][y],dp2[x][y],dp2[x][y]);
		}
	}
	
	int counter=0;
	for(int x=0;x<n;x++){
		counter+=max(dp[x][0],dp2[x][0]);
	}
	
	for(int y=1;y<m;y++){
		counter+=max(dp[n-1][y],dp2[n-1][y]);
	}
	
	cout << counter;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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