Submission #995954

#	Time	Username	Problem	Language	Result	Execution time	Memory
995954		yanb	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	2096 ms	456 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>

struct Stick {
    int x, y;
    bool r;
    vector<pii> pos;

    Stick(int x, int y, bool r) {
        this->x = x;
        this->y = y;
        this->r = r;
        if (r) {
            pos.push_back({x, y});
            pos.push_back({x, y + 1});
            pos.push_back({x, y + 2});
        } else {
            pos.push_back({x, y});
            pos.push_back({x + 1, y});
            pos.push_back({x + 2, y});
        }
    }

    bool operator&(const Stick &s) const {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (pos[i] == s.pos[j]) return 1;
            }
        }
        return 0;
    }
};

int solve(int n, vector<Stick> &a, int took, vector<bool> &was) {
    if (took == n) return 0;
    
    bool good = 1;
    for (int i = 0; i < took; i++) {
        if (was[i] && (a[i] & a[took])) {
            good = 0;
        }
    }

    was[took] = 0;
    int ans = solve(n, a, took + 1, was);
    if (good) {
        was[took] = 1;
        ans = max(ans, solve(n, a, took + 1, was) + 1);
    }
    return ans;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<char>> a(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    vector<Stick> cand;
    for (int i = 0; i < n - 2; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') cand.push_back(Stick(i, j, 0));
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 2; j++) {
            if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') cand.push_back(Stick(i, j, 1));
        }
    }

    vector<bool> was(cand.size());
    cout << solve(cand.size(), cand, 0, was) << "\n";
}   

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