Submission #678535

#	Time	Username	Problem	Language	Result	Execution time	Memory
678535		uylulu	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	130 ms	262144 KiB

dango_maker

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

#define ld long double
// #define int long long
#define endl "\n"

const int N = 3e3 + 5;

vector<int> adj[N*N];
char grid[N + 1][N + 1];    

struct p{
    int r,c;
};

map<pair<pair<int,int>,pair<int,int>>,int> mp;

int dp[N*N + 1][2];

int f(int s,int pa,bool type) {
    if(dp[s][type] != -1) return dp[s][type];

    int res = type;
    for(auto u : adj[s]) {
        if(u == pa) continue;
        
        res = (res + f(u,s,!type));
    }
    return dp[s][type] = res;
}

signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);

    int n,m;
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));

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

    int curr = 1;

    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            int cnt = 0;

            if(j <= m - 2 && grid[i][j] == 'R' && grid[i][j + 1] == 'G' && grid[i][j + 2] == 'W') {
                mp[{{i,j},{i,j + 2}}] = curr;
            
                // intersect G
                pair<pair<int,int>,pair<int,int>> tmp = {{i - 1,j + 1},{i + 1,j + 1}};
                if(mp[tmp]) {
                    adj[curr].push_back(mp[tmp]);
                    adj[mp[tmp]].push_back(curr);
                }
                // intersect W
                tmp = {{i - 2,j + 2},{i - 2,j}};
                if(mp[tmp]) {
                    adj[curr].push_back(mp[tmp]);
                    adj[mp[tmp]].push_back(curr);
                }

                curr++;
                cnt++;
            }
            if(i <= m - 2 && grid[i][j] == 'R' && grid[i + 1][j] == 'G' && grid[i + 2][j] == 'W') {
                mp[{{i,j},{i + 2,j}}] = curr;

                // intersect G
                pair<pair<int,int>,pair<int,int>> tmp = {{i + 1,j - 1},{i + 1,j + 1}};
                if(mp[tmp]) {
                    adj[curr].push_back(mp[tmp]);
                    adj[mp[tmp]].push_back(curr);
                }
                curr++;
                cnt++;
            }
            if(cnt == 2) {
                adj[curr - 2].push_back(curr - 1);
                adj[curr - 1].push_back(curr - 2);
            }
        }
    }
    int kq = 0;
    for(int i = 1;i < curr;i++) {
        if(dp[i][0] == -1) {
            kq += max(f(i,-1,0),f(i,-1,1));
        }
    }
    cout<<kq<<endl;


    return 0;
}    

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