Submission #1113776

#TimeUsernameProblemLanguageResultExecution timeMemory
1113776Dan4LifeDango Maker (JOI18_dango_maker)C++17
100 / 100
205 ms10576 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define sz(a) (int)a.size() #define all(a) begin(a),end(a) const int N = (int)3e3+2; int n, m, ans; string s[N]; int calc(int i, int j){ int x = i, y = j; vector<array<int,2>> v; v.clear(); v.pb({x,y}); while(x+1<n and y) x++, y--, v.pb({x,y}); reverse(all(v)); int dp[sz(v)+1][3]; for(int i = 0; i <= sz(v); i++) for(int j = 0; j < 3; j++) dp[i][j]=-N*N; dp[0][0] = dp[0][1] = dp[0][2] = 0; for(i = 1; i <= sz(v); i++){ dp[i][0] = max({dp[i-1][0],dp[i-1][1],dp[i-1][2]}); auto [x,y] = v[i-1]; if(y+2<m and s[x][y]=='R' and s[x][y+1]=='G' and s[x][y+2]=='W') dp[i][1] = max({dp[i-1][0],dp[i-1][1],dp[i-1][2]})+1; if(x+2<n and s[x][y]=='R' and s[x+1][y]=='G' and s[x+2][y]=='W'){ dp[i][2] = dp[i-1][2]+1; if(i>=2) dp[i][2] = max(dp[i][2], max(dp[i-2][0],dp[i-2][2])+1); } } return max({dp[sz(v)][0],dp[sz(v)][1],dp[sz(v)][2]}); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) cin >> s[i]; for(int j = 0; j < m; j++) ans+=calc(0,j); for(int i = 1; i < n; i++) ans+=calc(i,m-1); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...