#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" )
#pragma GCC optimize("unroll-loops")
/*
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
#pragma GCC optimize("vpt")
#pragma GCC optimize("rename-registers")
#pragma GCC optimize("move-loop-invariants")
#pragma GCC optimize("unswitch-loops")
#pragma GCC optimize("function-sections")
#pragma GCC optimize("data-sections")
#pragma GCC optimize("branch-target-load-optimize")
#pragma GCC optimize("branch-target-load-optimize2")
#pragma GCC optimize("btr-bb-exclusive")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define dauzhan gay
#define popcount __builtin_popcount
const long double Eps = 1e-12;
const int max1 = 1e9 + 100;
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 2e5 + 100;
const int B = 9000000 + 1;
const ll INF = 1e18 + 100;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
if(y < 0) return 0;
if(y == 0) return 1;
if(y == 1) return x;
if(y % 2 == 0) {
ll now = binpow(x,y/2,md);
return (1ll*now*now) % md;
}
else {
ll now = binpow(x,y/2,md);
return (1ll*((1ll*now*now) % md)*x) % md;
}
}
/*
for(int i = 1;i <= n;i++) sp[0][i] = a[i];
for(int i = 1;i <= log2(n);i++) {
for(int l = 1;l <= n;l++) {
int r = l + (1 << i) - 1;
if(r > n) break;
int middle = l + (1 << (i - 1));
sp[i][l] = max(sp[i - 1][l],sp[i - 1][middle]);
}
}
int get(int l,int r) {
int g = log2(r - l + 1);
return max(sp[g][l],sp[g][r - (1 << g) + 1]);
}
*/
int matching[B];
bool used[B];
vector <int> reb[B];
bool dfs(int v) {
if(used[v]) return false;
used[v] = true;
for(auto to:reb[v]) {
if(matching[to] == -1 || dfs(matching[to])) {
matching[to] = v;
return true;
}
}
return false;
}
int n,m;
int f(int x,int y) {
return (x - 1)*m + y;
}
pair <int,int> g(int x) {
int b = x % m;
if(b == 0) b = m;
return {(x - b)/m + 1,b};
}
signed main() {
ios_base::sync_with_stdio(NULL);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
char a[n + 1][m + 1];
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
cin >> a[i][j];
}
}
//a[i][j] = (i - 1)*m + j;
memset(matching,-1,sizeof(matching));
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(a[i][j] == 'G') {
if((i < n&&a[i + 1][j] == 'W') || (j < m&&a[i][j + 1] == 'W')) {
if(i > 1&&a[i - 1][j] == 'R') {
int x = f(i - 1,j);
int y = f(i,j);
reb[x].pb(y);
reb[y].pb(x);
}
if(j > 1&&a[i][j - 1] == 'R') {
int x = f(i,j - 1);
int y = f(i,j);
reb[x].pb(y);
reb[y].pb(x);
}
}
}
}
}
for(int i = 1;i <= n*m;i++) {
memset(used,false,sizeof(used));
dfs(i);
}
bool chose[n + 1][m + 1];
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
chose[i][j] = false;
}
}
for(int i = 1;i <= n*m;i++) {
if(matching[i] != -1) {
int x = i,y = matching[i];
int x1 = g(x).f,y1 = g(x).s;
int x2 = g(y).f,y2 = g(y).s;
if(a[x1][y1] == 'G') {
chose[x1][y1] = true;
}
if(a[x2][y2] == 'G') {
chose[x2][y2] = true;
}
}
}
int ans = 0;
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(a[i][j] == 'W') {
if(j > 1&&chose[i][j - 1]) {
chose[i][j - 1] = false;
ans++;
}
else if(i > 1&&chose[i - 1][j]) {
chose[i - 1][j] = false;
ans++;
}
}
}
}
cout << ans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 2 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 3 |
Correct |
108 ms |
255696 KB |
Output is correct |
| 4 |
Correct |
95 ms |
255712 KB |
Output is correct |
| 5 |
Correct |
97 ms |
255572 KB |
Output is correct |
| 6 |
Correct |
96 ms |
255568 KB |
Output is correct |
| 7 |
Correct |
108 ms |
255572 KB |
Output is correct |
| 8 |
Correct |
98 ms |
255708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
255572 KB |
Output is correct |
| 10 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 11 |
Correct |
103 ms |
255776 KB |
Output is correct |
| 12 |
Correct |
101 ms |
255840 KB |
Output is correct |
| 13 |
Correct |
97 ms |
255660 KB |
Output is correct |
| 14 |
Correct |
97 ms |
255792 KB |
Output is correct |
| 15 |
Correct |
98 ms |
255704 KB |
Output is correct |
| 16 |
Correct |
96 ms |
255588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 2 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 3 |
Correct |
108 ms |
255696 KB |
Output is correct |
| 4 |
Correct |
95 ms |
255712 KB |
Output is correct |
| 5 |
Correct |
97 ms |
255572 KB |
Output is correct |
| 6 |
Correct |
96 ms |
255568 KB |
Output is correct |
| 7 |
Correct |
108 ms |
255572 KB |
Output is correct |
| 8 |
Correct |
98 ms |
255708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
255572 KB |
Output is correct |
| 10 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 11 |
Correct |
103 ms |
255776 KB |
Output is correct |
| 12 |
Correct |
101 ms |
255840 KB |
Output is correct |
| 13 |
Correct |
97 ms |
255660 KB |
Output is correct |
| 14 |
Correct |
97 ms |
255792 KB |
Output is correct |
| 15 |
Correct |
98 ms |
255704 KB |
Output is correct |
| 16 |
Correct |
96 ms |
255588 KB |
Output is correct |
| 17 |
Correct |
105 ms |
255700 KB |
Output is correct |
| 18 |
Correct |
101 ms |
255568 KB |
Output is correct |
| 19 |
Incorrect |
104 ms |
255648 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 2 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 3 |
Correct |
108 ms |
255696 KB |
Output is correct |
| 4 |
Correct |
95 ms |
255712 KB |
Output is correct |
| 5 |
Correct |
97 ms |
255572 KB |
Output is correct |
| 6 |
Correct |
96 ms |
255568 KB |
Output is correct |
| 7 |
Correct |
108 ms |
255572 KB |
Output is correct |
| 8 |
Correct |
98 ms |
255708 KB |
Output is correct |
| 9 |
Correct |
95 ms |
255572 KB |
Output is correct |
| 10 |
Correct |
94 ms |
255568 KB |
Output is correct |
| 11 |
Correct |
103 ms |
255776 KB |
Output is correct |
| 12 |
Correct |
101 ms |
255840 KB |
Output is correct |
| 13 |
Correct |
97 ms |
255660 KB |
Output is correct |
| 14 |
Correct |
97 ms |
255792 KB |
Output is correct |
| 15 |
Correct |
98 ms |
255704 KB |
Output is correct |
| 16 |
Correct |
96 ms |
255588 KB |
Output is correct |
| 17 |
Correct |
105 ms |
255700 KB |
Output is correct |
| 18 |
Correct |
101 ms |
255568 KB |
Output is correct |
| 19 |
Incorrect |
104 ms |
255648 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
