Submission #1316071

#TimeUsernameProblemLanguageResultExecution timeMemory
1316071JuanJLDango Maker (JOI18_dango_maker)C++20
0 / 100
46 ms106420 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i < b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef int ll;

const int MAXN = 3000+5;

ll n,m;
string o = "RGW";

bool ver[MAXN][MAXN];
bool hor[MAXN][MAXN];

ll dp[MAXN][MAXN][3];

ll f(ll i, ll j, ll k){
	ll &res = dp[i][j][k];
	if(res!=-1) return res;
	if(i>=n ||j>=m) return 0;
	res=0;

	if(ver[i][j] && k == 0){
		res=max(res,f(i+1,j+1,0)+1);
	}

	if(hor[i][j]){
		res=max(res,f(i+1,j+1,2)+1);
	}

	res=max(res,f(i+1,j+1,max((ll)0,k-1)));

	return res;
}

int main(){
	cin>>n>>m;
	vector<string> s(n); forn(i,0,n) cin>>s[i];

	forn(i,0,n){
		forn(j,0,m){
			ver[i][j]=true;
			hor[i][j]=true;
			forn(h,0,3){
				if(i+h>=n || s[i+h][j]!=o[h]) ver[i][j]=false;
				if(j+h>=m || s[i][j+h]!=o[h]) hor[i][j]=false;
			}
		}
	}

	mset(dp,-1);

	ll res = 0;
	forn(i,0,n){
		res+=f(i,0,0);
	}
	forn(j,1,m){
		res+=f(0,j,0);
	}

	cout<<res<<'\n';
	
	return 0;
} 
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...