Submission #1181793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181793		anteknne	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	148 ms	9336 KiB

dango_maker

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 3000 + 17;
char a[MAXN][MAXN];
int dp[MAXN];
int dppion[MAXN];
int dppoziom[MAXN];

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }

    int wyn = 0;
    for (int i = 1; i <= n + m - 1; i ++) {
        int ind = 1;
        for (int j = min(i, n); j >= 0; j --) {
            if (i - j > m) {
                break;
            }

            dppion[ind] = max(dp[ind - 1], dppion[ind - 1]);
            dppoziom[ind] = max(dp[ind - 1], dppoziom[ind - 1]);
            dp[ind] = max(dppion[ind], dppoziom[ind]);

            if (j - 1 >= 1 && j + 1 <= n) {
                if (a[j - 1][i - j] == 'R' && a[j][i - j] == 'G' && a[j + 1][i - j] == 'W') {
                    dppion[ind] ++;
                }
            }
            if (i - j - 1 >= 1 && i - j + 1 <= m) {
                if (a[j][i - j - 1] == 'R'&& a[j][i - j] == 'G' && a[j][i - j + 1] == 'W') {
                    dppoziom[ind] ++;
                }
            }

            //cout << i << " " << ind << ": " << dp[ind] << " " << dppion[ind] << " " << dppoziom[ind] << "\n";

            ind ++;
        }

        wyn += max(dp[ind - 1], max(dppion[ind - 1], dppoziom[ind - 1]));

        memset(dp, 0, sizeof(dp));
        memset(dppoziom, 0, sizeof(dppoziom));
        memset(dppion, 0, sizeof(dppion));
    }

    cout << wyn << "\n";

    return 0;
}

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