oj.uz

Submission #780336

# Submission time Handle Problem Language Result Execution time Memory
780336 2023-07-12T08:21:23 Z mychecksedad Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 468 KB 
/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 1E7+100, M = 1e5+10, K = 20;


int n, m;
string s[4000];
bitset<3> g[N][2];
bitset<N> v[2];
bitset<N> vis[2];
vector<vector<int>> arr;

pair<int, int> dfs(int x, int p){
  pair<int, int> ans = {1, 0};
  // cout <<x/m << ' ' << x%m  << ' ' << p << '\n';
  vis[p][x] = 1;
  for(int y = 0; y < 3; ++y){
    if(!g[x][p][y]) continue;
    pair<int, int> u = {arr[p][y]+x, 1-p};
    if(vis[u.second][u.first]) continue;
    auto dp = dfs(u.first, u.second);
    ans.first += dp.second;
    ans.second += dp.first;
  }
  return ans;
}

void solve(){
  cin >> n >> m;

  arr = {
  {
    0, 
    m-1, 
    2*m-2 
    },
    { 
      0,
      -m+1,
      -2*m+2
    }
  };


  for(int i = 0; i < n; ++i) cin >> s[i];
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(i < n - 2){
        int x = i*m+j;
        if(s[i][j] == 'R' && s[i+1][j] == 'G' && s[i+2][j] == 'W'){
          if(v[1][x]) g[x][0][0] = 1, g[x][1][0] = 1;
          if(v[1][x+m]) g[x][0][1] = 1, g[x+m-1][1][1] = 1;
          if(v[1][x+m+m]) g[x][0][2] = 1, g[x+2*m-2][1][2] = 1;
          v[0][x] = v[0][x+m] = v[0][x+m+m] = 1;
        }
      }
      if(j < m-2){
        int x = i*m+j;

        if(s[i][j] == 'R' && s[i][j+1] == 'G' && s[i][j+2] == 'W'){
          if(v[0][x]) g[x][1][0] = 1, g[x][0][0] = 1;
          if(v[0][x+1]) g[x][1][1] = 1, g[x+1-m][0][1] = 1;
          if(v[0][x+2]) g[x][1][2] = 1, g[x+2-2*m][0][2] = 1;
          v[1][x] = v[1][x+1] = v[1][x+2] = 1;
        }
      }
    }
  }
  int ans = 0;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(s[i][j] != 'R') continue;
      if(!vis[0][i*m+j] && v[0][i*m+j]){
        auto dp = dfs(i*m+j, 0);
        ans += max(dp.first, dp.second);
        // cout << i << ' ' << j << ' '<< ' ' << 0 << ' ' << ans << '\n';
      }else if(!vis[1][i*m+j] && v[1][i*m+j]){
         auto dp = dfs(i*m+j, 1);
        ans += max(dp.first, dp.second);
        // cout << i << ' ' << j << ' '<< ' ' << 1 << ' ' << ans << '\n';
      }
    }
  }
  cout << ans;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int T = 1, aa;
  // cin >> T;aa=T;
  while(T--){
    // cout << "Case #" << aa-T << ": ";
    solve();
  }
  return 0;
 
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:96:14: warning: unused variable 'aa' [-Wunused-variable]
   96 |   int T = 1, aa;
      |              ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 456 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 456 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 0 ms 456 KB Output is correct
32 Correct 0 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Incorrect 1 ms 456 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 456 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 452 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 0 ms 468 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 456 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 456 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 1 ms 468 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 0 ms 456 KB Output is correct
32 Correct 0 ms 468 KB Output is correct
33 Correct 1 ms 468 KB Output is correct
34 Incorrect 1 ms 456 KB Output isn't correct
35 Halted 0 ms 0 KB -