oj.uz

Submission #678539

# Submission time Handle Problem Language Result Execution time Memory
678539 2023-01-06T07:01:56 Z uylulu Dango Maker (JOI18_dango_maker) C++17
0 / 100
 133 ms 246924 KB 
#include <bits/stdc++.h>
using namespace std;

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

const int N = 3e3;

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

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.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 246800 KB Output is correct
2 Correct 117 ms 246852 KB Output is correct
3 Correct 107 ms 246792 KB Output is correct
4 Correct 108 ms 246924 KB Output is correct
5 Correct 109 ms 246864 KB Output is correct
6 Incorrect 108 ms 246860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 246800 KB Output is correct
2 Correct 117 ms 246852 KB Output is correct
3 Correct 107 ms 246792 KB Output is correct
4 Correct 108 ms 246924 KB Output is correct
5 Correct 109 ms 246864 KB Output is correct
6 Incorrect 108 ms 246860 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 246800 KB Output is correct
2 Correct 117 ms 246852 KB Output is correct
3 Correct 107 ms 246792 KB Output is correct
4 Correct 108 ms 246924 KB Output is correct
5 Correct 109 ms 246864 KB Output is correct
6 Incorrect 108 ms 246860 KB Output isn't correct
7 Halted 0 ms 0 KB -