Submission #1167900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167900		CrabCNH	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	171 ms	35820 KiB

dango_maker

#include <bits/stdc++.h>

#define task   "BriantheCrab"

#define int    long long
#define pii    pair <int, int>
#define fi     first
#define se     second
#define szf    sizeof
#define sz(s)  (int)((s).size())

using namespace std;

template <class T> void mini (T &t, T f) {if (t > f) t = f;}
template <class T> void maxi (T &t, T f) {if (t < f) t = f;}

const int maxN = 3e3 + 5;
const int inf = 1e18 + 7;
const int mod = 1e9 + 7;

int n, m;
char a[maxN][maxN];
bool visited[maxN][maxN];
bool t1[maxN][maxN], t2[maxN][maxN];;
vector <pair <bool, bool>> all;
int dp[maxN][3];

bool isValid (int x, int y) {
    return (x >= 1 && y >= 1 && x <= n && y <= m);
}

void solve () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (a[i][j] == 'G' && a[i][j - 1] == 'R' && a[i][j + 1] == 'W') {
                t1[i][j] = 1;
            }
            if (a[i][j] == 'G' && a[i - 1][j] == 'R' && a[i + 1][j] == 'W') {
                t2[i][j] = 1;
            }
        }
    }
    int res = 0;
    //cout << ((t1[2][4] || t2[2][4]) && isValid (2, 4) && !visited[2][4]) << '\n';
    for (int x = 1; x <= n; x ++) {
        for (int y = 1; y <= m; y ++) {
            int curX = x, curY = y;
            all.clear ();
            //cout << curX << ' ' << curY << ' ' << visited[curX][curY] << '\n';
            while ((t1[curX][curY] || t2[curX][curY]) && isValid (curX, curY) && !visited[curX][curY]) {
                all.push_back ({t1[curX][curY], t2[curX][curY]});
                visited[curX][curY] = 1;
                //cout << curX << ' ' << curY << '\n';
                curX ++;
                curY --;
            }
            //cout << "end \n";
            if (all.size () >= 1) {
                int best = 0;
                for (int i = 0; i < (int) all.size (); i ++) {
                    dp[i][0] = dp[i][1] = dp[i][2] = -inf;
                }
                dp[0][0] = 0;
                dp[0][1] = (all[0].fi ? 1 : -inf);
                maxi (best, dp[0][1]);
                dp[0][2] = (all[0].se ? 1 : -inf);
                maxi (best, dp[0][2]);
                for (int i = 1; i < (int) all.size (); i ++) {
                    dp[i][0] = max ({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
                    if (all[i].fi) {
                        dp[i][1] = max (dp[i - 1][0], dp[i - 1][1]) + 1;
                    }
                    if (all[i].se) {
                        dp[i][2] = max (dp[i - 1][0], dp[i - 1][2]) + 1;
                    }
                    maxi (best, max ({dp[i][0], dp[i][1], dp[i][2]}));
                }
                // for (int i = 0; i < (int) all.size (); i ++) {
                    // cout << dp[i][1] << ' ' << dp[i][2] << ' ' << dp[i][3] << '\n';
                // }
                res += best;
            }
        }
    }
    cout << res;
    return;
}

signed main () {
    cin.tie (nullptr) -> sync_with_stdio (false);
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    int t = 1;
    //cin >> t;
    while (t --) {
        solve ();
    } 
    return 0;
}
// thfdgb

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:98:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:99:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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