Submission #442656

#TimeUsernameProblemLanguageResultExecution timeMemory
442656arujbansalDango Maker (JOI18_dango_maker)C++17
100 / 100
305 ms123744 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() // #define int long long const int MXN = 3e3 + 5, INF = 1e9 + 5; int N, M; char grid[MXN][MXN]; int dp[MXN][MXN][3]; bool skewer_down(int i, int j) { return (grid[i - 1][j] == 'R' && grid[i][j] == 'G' && grid[i + 1][j] == 'W'); } bool skewer_right(int i, int j) { return (grid[i][j - 1] == 'R' && grid[i][j] == 'G' && grid[i][j + 1] == 'W'); } void solve() { cin >> N >> M; for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) cin >> grid[i][j]; for (int i = 1; i <= N; i++) { for (int j = 1; j <= M; j++) { for (int k = 0; k < 3; k++) dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j + 1][k]); if (skewer_down(i, j)) dp[i][j][1] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]) + 1; if (skewer_right(i, j)) dp[i][j][2] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][2]) + 1; } } int ans = 0; for (int i = 1; i <= N; i++) ans += max({dp[i][1][0], dp[i][1][1], dp[i][1][2]}); for (int j = 2; j <= M; j++) ans += max({dp[N][j][0], dp[N][j][1], dp[N][j][2]}); cout << ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...