Submission #1099518

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099518		underwaterkillerwhale	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	348 KiB

dango_maker

//#include"holiday.h"
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 2e3 + 7;
int Mod = 1e9 + 7;///lon
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 450;

int n, m;
char a[N][N];
bool dd[N][N];
int res = 0;

bool dango (pii x, pii y, pii z) {
    if (dd[x.fs][x.se] || dd[y.fs][y.se] || dd[z.fs][z.se]) return 0;
    if (a[x.fs][x.se] != 'R' || a[y.fs][y.se] != 'G' || a[z.fs][z.se] != 'W') return 0;
    return 1;
}

void calc (int x, int y, int u, int v) {
    rep (j, y, v) {
        ///ngang tren
        if (x >= 3 && dango(MP(x - 2, j), MP(x - 1, j), MP(x, j))) {
            ++res;
            dd[x][j] = dd[x - 1][j] = dd[x - 2][j] = 1;
        }
        ///ngang duoi
        if (u <= n - 2 && dango(MP(u, j), MP(u + 1, j), MP(u + 2, j))) {
            ++res;
            dd[u][j] = dd[u + 1][j] = dd[u + 2][j] = 1;
        }
    }
    rep (i, x, u) {
        ///doc trai
        if (y >= 3 && dango(MP(i, y - 2), MP(i, y - 1), MP(i, y))) {
            ++res;
            dd[i][y - 2] = dd[i][y - 1] = dd[i][y] = 1;
        }
        ///doc phai
        if (v <= m - 2 && dango(MP(i, v), MP(i, v + 1), MP(i, v + 2))) {
            ++res;
            dd[i][v] = dd[i][v + 1] = dd[i][v + 2] = 1;
        }
    }
    rep (j, y, v) {
        if (dango(MP(x, j), MP(x, j + 1), MP(x, j + 2))) {
            ++res;
            dd[x][j] = dd[x][j + 1] = dd[x][j + 2] = 1;
        }
        if (dango(MP(u, j), MP(u, j + 1), MP(u, j + 2))) {
            ++res;
            dd[u][j] = dd[u][j + 1] = dd[u][j + 2] = 1;
        }
    }
    rep (i, x, u) {
        if (dango(MP(i, y), MP(i + 1, y), MP(i + 2, y))) {
            ++res;
            dd[i][y] = dd[i + 1][y] = dd[i + 2][y] = 1;
        }
        if (dango(MP(i, v), MP(i + 1, v), MP(i + 2, v))) {
            ++res;
            dd[i][v] = dd[i + 1][v] = dd[i + 2][v] = 1;
        }
    }
    if (x + 1 == u) {
        rep (j, y, v) {
            ///ngang tren
            if (x <= n - 2 && dango(MP(x, j), MP(x + 1, j), MP(x + 2, j))) {
                ++res;
                dd[x][j] = dd[x + 1][j] = dd[x + 2][j] = 1;
            }
            ///ngang duoi
            if (u >= 3 && dango(MP(u - 2, j), MP(u - 1, j), MP(u, j))) {
                ++res;
                dd[u][j] = dd[u - 1][j] = dd[u - 2][j] = 1;
            }
        }
    }
    if (y + 1 == v) {
        rep (i, x, u) {
            if (y <= m - 2 && dango(MP(i, y), MP(i, y + 1), MP(i, y + 2))) {
                ++res;
                dd[i][y] = dd[i][y + 1] = dd[i][y + 2] = 1;
            }
            if (v >= 2 && dango(MP(i, v - 2), MP(i, v - 1), MP(i, v))) {
                ++res;
                dd[i][v - 2] = dd[i][v - 1] = dd[i][v] = 1;
            }
        }
    }
    if (x + 1 >= u || y + 1 >= v)
        return;
    calc(x + 1, y + 1, u - 1, v - 1);
}
void solution () {
    cin >> n >> m;
    rep (i, 1, n) {
        string S;
        cin >> S;
        rep (j, 1, m) {
            a[i][j] = S[j - 1];
        }
    }
    calc(1, 1, n, m);
//    rep (i, 1, n)
//    rep (j, 1, m) {
//        cout << dd[i][j] <<" \n"[j == m];
//    }
    cout << res <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +10

5 5
01101
10001
00110
10101
00100
*/

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