Submission #75479

# Submission time Handle Problem Language Result Execution time Memory
75479 2018-09-09T21:33:10 Z vex Dango Maker (JOI18_dango_maker) C++14
0 / 100
188 ms 212688 KB
#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)
{
    dp[v][0]=0;
    dp[v][1]=1;
    bio[v]=true;

    for(auto x:adj[v])
    {
        if(bio[v])continue;
        dfs(x);
        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++)bio[i]=false;
    for(int i=0;i<uk;i++)if(!bio[i])
    {
        dfs(i);
        sol+=max(dp[i][0],dp[i][1]);
    }

    cout<<sol<<endl;
    return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 186 ms 212344 KB Output is correct
2 Correct 188 ms 212492 KB Output is correct
3 Correct 186 ms 212672 KB Output is correct
4 Correct 183 ms 212672 KB Output is correct
5 Correct 185 ms 212672 KB Output is correct
6 Incorrect 188 ms 212688 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 186 ms 212344 KB Output is correct
2 Correct 188 ms 212492 KB Output is correct
3 Correct 186 ms 212672 KB Output is correct
4 Correct 183 ms 212672 KB Output is correct
5 Correct 185 ms 212672 KB Output is correct
6 Incorrect 188 ms 212688 KB Output isn't correct
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 186 ms 212344 KB Output is correct
2 Correct 188 ms 212492 KB Output is correct
3 Correct 186 ms 212672 KB Output is correct
4 Correct 183 ms 212672 KB Output is correct
5 Correct 185 ms 212672 KB Output is correct
6 Incorrect 188 ms 212688 KB Output isn't correct
7 Halted 0 ms 0 KB -