Submission #609328

#	Time	Username	Problem	Language	Result	Execution time	Memory
609328		urosk	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	1 ms	468 KiB

dango_maker

#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
*/
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 3005
#define maxx 10000005
ll n,m;
ll a[maxn][maxn];
ll id[maxn][maxn][2];
bool col[maxn][maxn][2];
bool vis[maxn][maxn][2];
ll it = 1;
bool okright(ll i,ll j){
    if(j+2>m) return 0;
    return (a[i][j]==1)&&(a[i][j+1]==2)&&(a[i][j+2]==3);
}
bool okdown(ll i,ll j){
    if(i+2>n) return 0;
    return (a[i][j]==1)&&(a[i+1][j]==2)&&(a[i+2][j]==3);
}
bool valid(ll i,ll j){
    return i>=1&&i<=n&&j>=1&&j<=m;
}
pll mrg(pll a,pll b){
    return {a.fi+b.fi,a.sc+b.sc};
}
pll dfs(ll i,ll j,bool r,ll ipar,ll jpar,bool rpar){
    //cerr<<i<< " "<<j<<" "<<r<<endl;
    vis[i][j][r] = 1;
    col[i][j][r] = col[ipar][jpar][rpar]^1;
    pll p = {1,(col[i][j][r]==1)};
    if(id[i][j][1]&&id[i][j][0]&&!vis[i][j][r^1]) p = mrg(p,dfs(i,j,r^1,i,j,r));
    if(r==1){
        for(ll e = 1;e<=2;e++){
            if(valid(i-e,j+e)&&id[i-e][j+e][r^1]&&!vis[i-e][j+e][r^1]) p = mrg(p,dfs(i-e,j+e,r^1,i,j,r));
        }
    }else{
        for(ll e = -2;e<=-1;e++){
            if(valid(i-e,j+e)&&id[i-e][j+e][r^1]&&!vis[i-e][j+e][r^1]) p = mrg(p,dfs(i-e,j+e,r^1,i,j,r));
        }
    }
    return p;
}
ll ans = 0;
int main(){
	daj_mi_malo_vremena
    cin >> n >> m;
    for(ll i = 1;i<=n;i++){
        string s; cin >> s;
        for(ll j = 1;j<=m;j++){
            if(s[j-1]=='R') a[i][j] = 1;
            if(s[j-1]=='G') a[i][j] = 2;
            if(s[j-1]=='W') a[i][j] = 3;
        }
    }
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            if(a[i][j]!=1) continue;
            if(okright(i,j)) id[i][j][1] = it++;
            if(okdown(i,j)) id[i][j][0] = it++;
        }
    }
    /*
    here;
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++) cerr<<id[i][j][0]<< " ";
        cerr<<endl;
    }
    here;
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++) cerr<<id[i][j][1]<< " ";
        cerr<<endl;
    }
    here;
    */
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            for(ll k = 0;k<=1;k++){
                if(vis[i][j][k]) continue;
                if(id[i][j][k]){
                    //here;
                    pll p = dfs(i,j,k,i,j,k);
                    ans+=max(p.fi-p.sc,p.sc);
                }
            }
        }
    }
    cout<<ans<<endl;
	return 0;
}
/*
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
4 4
RGWR
GRRG
WGGW
WWWR
3 4
RGWR
GRGG
RGWW
*/

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67