Submission #1289730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289730		hasandas	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	580 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

int greedy_scan(const vector<string>& v, int n, int m, bool horizontal_first) {
    vector<char> used(n * m, 0);
    int cnt = 0;
    if (horizontal_first) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j + 2 < m; ++j)
                if (!used[i*m + j] && !used[i*m + (j+1)] && !used[i*m + (j+2)] &&
                    v[i][j]=='R' && v[i][j+1]=='G' && v[i][j+2]=='W') {
                    used[i*m + j] = used[i*m + (j+1)] = used[i*m + (j+2)] = 1;
                    ++cnt;
                }
        for (int i = 0; i + 2 < n; ++i)
            for (int j = 0; j < m; ++j)
                if (!used[i*m + j] && !used[(i+1)*m + j] && !used[(i+2)*m + j] &&
                    v[i][j]=='R' && v[i+1][j]=='G' && v[i+2][j]=='W') {
                    used[i*m + j] = used[(i+1)*m + j] = used[(i+2)*m + j] = 1;
                    ++cnt;
                }
    }
    else {
        for (int i = 0; i + 2 < n; ++i)
            for (int j = 0; j < m; ++j)
                if (!used[i*m + j] && !used[(i+1)*m + j] && !used[(i+2)*m + j] &&
                    v[i][j]=='R' && v[i+1][j]=='G' && v[i+2][j]=='W') {
                    used[i*m + j] = used[(i+1)*m + j] = used[(i+2)*m + j] = 1;
                    ++cnt;
                }
        for (int i = 0; i < n; ++i)
            for (int j = 0; j + 2 < m; ++j)
                if (!used[i*m + j] && !used[i*m + (j+1)] && !used[i*m + (j+2)] &&
                    v[i][j]=='R' && v[i][j+1]=='G' && v[i][j+2]=='W') {
                    used[i*m + j] = used[i*m + (j+1)] = used[i*m + (j+2)] = 1;
                    ++cnt;
                }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<string> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];

    if (n <= 0 || m <= 0) {
        cout << 0 << '\n';
        return 0;
    }

    int maybeans = max(greedy_scan(v, n, m, true), greedy_scan(v, n, m, false));

    vector<array<int,3>> seg;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j + 2 < m; ++j) {
            if (v[i][j]=='R' && v[i][j+1]=='G' && v[i][j+2]=='W') {
                seg.push_back({i*m + j, i*m + (j+1), i*m + (j+2)});
            }
        }
    }
    for (int i = 0; i + 2 < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (v[i][j]=='R' && v[i+1][j]=='G' && v[i+2][j]=='W') {
                seg.push_back({i*m + j, (i+1)*m + j, (i+2)*m + j});
            }
        }
    }

    int P = (int)seg.size();
    if (P == 0) {
        cout << 0 << '\n';
        return 0;
    }

    vector<int> cc(n * m, 0);
    for (int id = 0; id < P; ++id) {
        auto &s = seg[id];
        cc[s[0]]++;
        cc[s[1]]++;
        cc[s[2]]++;
    }
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    for (int id = 0; id < P; ++id) {
        auto &s = seg[id];
        int loss = cc[s[0]] + cc[s[1]] + cc[s[2]] - 3;
        pq.push({loss, id});
    }

    vector<char> ac(n*m, 0);
    vector<char> segt(P, 0);
    int chosen = 0;

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int id = cur.second;
        if (segt[id]) continue;
        auto &s = seg[id];
        if (ac[s[0]] || ac[s[1]] || ac[s[2]]) continue;
        int curr_loss = cc[s[0]] + cc[s[1]] + cc[s[2]] - 3;
        if (curr_loss != cur.first) {
            pq.push({curr_loss, id});
            continue;
        }
        segt[id] = 1;
        ++chosen;
        ac[s[0]] = ac[s[1]] = ac[s[2]] = 1;
        cc[s[0]] = max(0, cc[s[0]] - 1);
        cc[s[1]] = max(0, cc[s[1]] - 1);
        cc[s[2]] = max(0, cc[s[2]] - 1);
    }

    int mightbeans = chosen;
    int ans = max(maybeans, mightbeans);
    cout << ans << '\n';
    return 0;
}

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