제출 #75473

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
75473		vex	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	205 ms	212904 KiB

dango_maker

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

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

int r[maxn][maxn];
int d[maxn][maxn];

int uk=0;
vector<int>adj[maxn*maxn];

int dp[maxn*maxn][2];
bool bio[maxn*maxn];

void dfs(int v,int p)
{
    dp[v][0]=0;
    dp[v][1]=1;
    bio[v]=true;

    for(auto x:adj[v])
    {
        if(x==p)continue;
        dfs(x,v);
        dp[v][0]+=max(dp[x][0],dp[x][1]);
        dp[v][1]+=dp[x][0];
    }
}

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

    cin>>n>>m;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++)cin>>a[i][j];

    for(int i=0;i<n;i++)for(int j=0;j<m;j++)
    {
        if(j+2<m && a[i][j]=='R' && a[i][j+1]=='G' && a[i][j+2]=='W')
        {
            r[i][j]=uk;
            uk++;
        }
        else r[i][j]=-1;

        if(i+2<n && a[i][j]=='R' && a[i+1][j]=='G' && a[i+2][j]=='W')
        {
            d[i][j]=uk;
            uk++;
        }
        else d[i][j]=-1;
    }

    /*for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)cout<<d[i][j]<<","<<r[i][j]<<" ";
        cout<<endl;
    }*/

    for(int i=0;i<n;i++)for(int j=0;j<m;j++)
    {
        if(d[i][j]!=-1)
        {
            if(r[i][j]!=-1)adj[d[i][j]].push_back(r[i][j]);
            if(j-1>=0 && r[i+1][j-1]!=-1)adj[d[i][j]].push_back(r[i+1][j-1]);
            if(j-2>=0 && r[i+2][j-2]!=-2)adj[d[i][j]].push_back(r[i+2][j-2]);
        }

        if(r[i][j]!=-1)
        {
            if(d[i][j]!=-1)adj[r[i][j]].push_back(d[i][j]);
            if(i-1>=0 && d[i-1][j+1]!=-1)adj[r[i][j]].push_back(d[i-1][j+1]);
            if(i-2>=0 && d[i-2][j+2]!=-1)adj[r[i][j]].push_back(d[i-2][j+2]);
        }
    }

    int sol=0;
    for(int i=0;i<uk;i++)if(!bio[i])
    {
        dfs(i,i);
        sol+=max(dp[i][0],dp[i][1]);
    }

    cout<<sol<<endl;
    return 0;
}

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