제출 #679899

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
679899		vjudge1	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2044 ms	9044 KiB

dango_maker

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

#define F first
#define S second
#define pb push_back
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int, int> ii;

void print() {cerr << '\n';} template <typename T1, typename... T2>
void print(const T1 &a, const T2 &...b) { cerr << a << ' ', print(b...); }

const int N = 3000 + 5;
const int mod = 1e9 + 7;

char a[N][N];
int n, m;

namespace sub12
{
class matching
{
private:
    int n, t;
    vector<vector<int>> a;
    vector<int> vis, assigned;
public:
    matching(int n)
    {
        t = 0;
        this -> n = n;
        a.resize(n + 1);
        vis.resize(n + 1);
        assigned.resize(n + 1);
    }
    void add(int u, int v)
    {
        a[u].pb(v);
    }
    bool visit(int u)
    {
        if (vis[u] != t) vis[u] = t;
        else return 0;

        for (int &v : a[u]) if (!assigned[v] || visit(assigned[v]))
        {
            assigned[v] = u;
            return 1;
        }
        return 0;
    }
    int match()
    {
        int res = 0;
        for(int i(0); i <= n; i++)
        {
            t++;
            res += visit(i);
        }
        return res;
    }
};

void solve()
{
    vector<ii> s, t;
    for (int i = 0; i < n; i++)
        for (int j = 0; j + 2 < m; j++)
        {
            if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W')
                s.pb({i, j});
            //print(i, j);
        }
    for (int j = 0; j < m; j++)
        for (int i = 0; i + 2 < n; i++)
        {
            if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W')
                t.pb({i, j});
            //print(i, j);
        }
    
    matching graph(s.size() + t.size());
    for (int i = 0; i < (int)s.size(); i++)
        for (int j = 0; j < (int)t.size(); j++)
        {
            bool ok = 0;
            for (int x = t[j].F; x <= t[j].F + 2; x++)
                for (int y = s[i].S; y <= s[i].S + 2; y++)
                    if (s[i].F == x && t[j].S == y) ok = 1;
                    
            if (ok) graph.add(i, j);
        }
    cout << s.size() + t.size() - graph.match();
}
}

void solve()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    sub12::solve();
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    return 0;
}

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