Submission #1185412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185412		patgra	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	118 ms	10256 KiB

dango_maker

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int h, w;
vector<string> arr;
array<array<int, 3>, 2> dp; // [ ind ] [ last is {none, hor, ver} ]

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> h >> w;
    arr.resize(h);
    rep(i, 0, h) cin >> arr[i];

    int ans = 0;
    rep(i, 0, h + w) {
        vector<int> gs;
        rep(j, 0, min(h, i + 1)) if(i - j < w && arr[j][i - j] == 'G' && ((j - 1 >= 0 && j + 1 < h && arr[j - 1][i - j] == 'R' && arr[j + 1][i - j] == 'W') || (i - j - 1 >= 0 && i - j + 1 < w && arr[j][i - j - 1] == 'R' && arr[j][i - j + 1] == 'W'))) gs.pb(j);
        DC << "diagonal " << i << eol;
        while(!gs.empty()) {
            int gi = (int)gs.size() - 1;
            while(gi && gs[gi - 1] == gs[gi] - 1) gi--;
            int add = 0;
            rep(k1, 0, 2) rep(k2, 0, 3) dp[k1][k2] = 0;
            DC << ' ';
            DEBUG rep(j, gi, (int)gs.size()) DC << gs[j] << ' ';
            DC << eol;
            DC << "  ";
            DEBUG rep(k, 0, 3) DC << dp[1 ^ gi & 1][k] << ' ';
            DC << eol;
            rep(j, gi, (int)gs.size()) {
                dp[j & 1][0] = max({dp[1 ^ j & 1][0], dp[1 ^ j & 1][1], dp[1 ^ j & 1][2]});
                auto x = gs[j], y = i - gs[j];
                dp[j & 1][1] = (x && x < h - 1 && arr[x - 1][y] == 'R' && arr[x + 1][y] == 'W') ? max(dp[1 ^ j & 1][0], dp[1 ^ j & 1][1]) + 1 : -1;
                dp[j & 1][2] = (y && y < w - 1 && arr[x][y - 1] == 'R' && arr[x][y + 1] == 'W') ? max(dp[1 ^ j & 1][0], dp[1 ^ j & 1][2]) + 1 : -1;
                rep(k, 0, 3) add = max(add, dp[j & 1][k]);
                DC << "  ";
                DEBUG rep(k, 0, 3) DC << dp[j & 1][k] << ' ';
                DC << eol;
            }
            ans += add;
            while((int)gs.size() > gi) gs.pop_back();
        }
    }
    cout << ans << '\n';
}

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