Submission #609471

#	Time	Username	Problem	Language	Result	Execution time	Memory
609471		urosk	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	387 ms	61272 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 dp[maxn][2][2];
bool moe[maxn][maxn][2];
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);
}
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++){
            moe[i+j][i][0] = okright(i,j);
            moe[i+j][i][1] = okdown(i,j);
        }
    }
    for(ll z = 2;z<=n+m;z++){
        for(ll i = 1;i<=n;i++) for(ll x = 0;x<=1;x++) for(ll y = 0;y<=1;y++) dp[i][x][y] = -llinf;
        dp[0][0][0] = 0;
        for(ll i = 1;i<=n;i++){
            for(ll x = 0;x<=1;x++){
                for(ll y = 0;y<=1;y++){
                    dp[i][0][x] = max(dp[i][0][x],dp[i-1][x][y]);
                    if(moe[z][i][0]&&x==0&&y==0) dp[i][0][x] = max(dp[i][0][x],dp[i-1][x][y]+1);
                    if(moe[z][i][1]) dp[i][1][x] = max(dp[i][1][x],dp[i-1][x][y]+1);
                }
            }
        }
        ll cur = 0;
        for(ll x = 0;x<=1;x++) for(ll y = 0;y<=1;y++) cur = max(cur,dp[n][x][y]);
        ans+=cur;
    }
    cout<<ans<<endl;
	return 0;
}
/*
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
4 4
RGWR
GRRG
WGGW
WWWR
3 4
RGWR
GRGG
RGWW
*/

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:78:92: warning: overflow in conversion from 'long long int' to 'int' changes value from '-100000000000000000' to '-1569325056' [-Woverflow]
   78 |         for(ll i = 1;i<=n;i++) for(ll x = 0;x<=1;x++) for(ll y = 0;y<=1;y++) dp[i][x][y] = -llinf;
      |                                                                                            ^

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