Submission #164525

#	Time	Username	Problem	Language	Result	Execution time	Memory
164525		balbit	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	3 ms	632 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i = n-1; i>=0; i--)
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define pb push_back
#ifdef BALBIT
#define IOS()
#define bug(x) cerr<<__LINE__<<' '<<#x<<": "<<x<<endl
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(x)
#endif

const ll mod = 1e9+7;
const int maxn = 3e3+5;
//const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;


	


char grd[maxn][maxn];

bool up[maxn][maxn];
bool rt[maxn][maxn];
int dp[maxn][maxn][2];



signed main(){
	IOS();
	int n, m; cin>>n>>m;
	
	REP(i,n) REP(j,m) cin>>grd[i][j];
	int nup = 0, nrt = 0;

	REP(i,n)REP(j,m){

		if(grd[i][j]=='G'){
			if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) {
				up[i][j] = 1;
			}
			if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) {
				rt[i][j] = 1;
			}
		}
	}

	vector<pii> st;
	REP(i,n*2) REP(j,m){
		if (i-j < n &&i-j>=0) st.pb({i-j+1,j+1});
	}

	
	ll re = 0;
	for (pii & ele: st){
		int i = ele.f, j = ele.s;
//		cout<<i<<' '<<j<<endl;
		dp[i][j][0] = dp[i][j][1] = max(dp[i+1][j-1][0], dp[i+1][j-1][1]);
		if (up[i-1][j-1]) MX(dp[i][j][0] , 1 + dp[i+1][j-1][0]);
		if (rt[i-1][j-1]) MX(dp[i][j][1] , 1 + dp[i+1][j-1][1]);
		if (i==1 || j == m){
			re += max(dp[i][j][0], dp[i][j][1]);
		}
	}
//	REP(i,n+1) REP(j,m+1){
//		cout<<dp[i][j][0]<<" \n"[j==m];
//	}
	cout<<re<<endl;
	
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:46:6: warning: unused variable 'nup' [-Wunused-variable]
  int nup = 0, nrt = 0;
      ^~~
dango_maker.cpp:46:15: warning: unused variable 'nrt' [-Wunused-variable]
  int nup = 0, nrt = 0;
               ^~~

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