oj.uz

Submission #75473

# Submission time Handle Problem Language Result Execution time Memory
75473 2018-09-09T21:26:21 Z vex Dango Maker (JOI18_dango_maker) C++14
13 / 100
 205 ms 212904 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,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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 212472 KB Output is correct
2 Correct 184 ms 212472 KB Output is correct
3 Correct 184 ms 212488 KB Output is correct
4 Correct 205 ms 212720 KB Output is correct
5 Correct 185 ms 212720 KB Output is correct
6 Correct 185 ms 212720 KB Output is correct
7 Correct 184 ms 212720 KB Output is correct
8 Correct 183 ms 212720 KB Output is correct
9 Correct 181 ms 212720 KB Output is correct
10 Correct 185 ms 212720 KB Output is correct
11 Correct 192 ms 212744 KB Output is correct
12 Correct 184 ms 212744 KB Output is correct
13 Correct 184 ms 212744 KB Output is correct
14 Correct 184 ms 212744 KB Output is correct
15 Correct 187 ms 212744 KB Output is correct
16 Correct 187 ms 212744 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 212472 KB Output is correct
2 Correct 184 ms 212472 KB Output is correct
3 Correct 184 ms 212488 KB Output is correct
4 Correct 205 ms 212720 KB Output is correct
5 Correct 185 ms 212720 KB Output is correct
6 Correct 185 ms 212720 KB Output is correct
7 Correct 184 ms 212720 KB Output is correct
8 Correct 183 ms 212720 KB Output is correct
9 Correct 181 ms 212720 KB Output is correct
10 Correct 185 ms 212720 KB Output is correct
11 Correct 192 ms 212744 KB Output is correct
12 Correct 184 ms 212744 KB Output is correct
13 Correct 184 ms 212744 KB Output is correct
14 Correct 184 ms 212744 KB Output is correct
15 Correct 187 ms 212744 KB Output is correct
16 Correct 187 ms 212744 KB Output is correct
17 Correct 182 ms 212748 KB Output is correct
18 Correct 190 ms 212752 KB Output is correct
19 Incorrect 193 ms 212904 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 212472 KB Output is correct
2 Correct 184 ms 212472 KB Output is correct
3 Correct 184 ms 212488 KB Output is correct
4 Correct 205 ms 212720 KB Output is correct
5 Correct 185 ms 212720 KB Output is correct
6 Correct 185 ms 212720 KB Output is correct
7 Correct 184 ms 212720 KB Output is correct
8 Correct 183 ms 212720 KB Output is correct
9 Correct 181 ms 212720 KB Output is correct
10 Correct 185 ms 212720 KB Output is correct
11 Correct 192 ms 212744 KB Output is correct
12 Correct 184 ms 212744 KB Output is correct
13 Correct 184 ms 212744 KB Output is correct
14 Correct 184 ms 212744 KB Output is correct
15 Correct 187 ms 212744 KB Output is correct
16 Correct 187 ms 212744 KB Output is correct
17 Correct 182 ms 212748 KB Output is correct
18 Correct 190 ms 212752 KB Output is correct
19 Incorrect 193 ms 212904 KB Output isn't correct
20 Halted 0 ms 0 KB -