Submission #260236

#	Time	Username	Problem	Language	Result	Execution time	Memory
260236		Goolakh	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	545 ms	79992 KiB

dango_maker

// FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2,no-stack-protector,unroll-loops,fast-math")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=3e3+10, maxm=5e4+10, lg=21, mod=1e9+7, inf=1e18;

ll n,m,t[maxn][maxn];
pll dp[maxn];
bool ral(ll i,ll j){return i>=0 && j>=0 && t[i][j]==1 && t[i][j+1]==2 && t[i][j+2]==3;}
bool cal(ll i,ll j){return i>=0 && j>=0 && t[i][j]==1 && t[i+1][j]==2 && t[i+2][j]==3;}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>m;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		char c; cin>>c;
		t[i][j]=(c=='R' ? 1:(c=='G' ? 2:3));
	}
	ll ans=0;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++){
		vector<pll> v;
		for(int k=0;i+k<n && k<=j;k++){
			if(t[i+k][j-k]!=2) break;
			v.pb({i+k,j-k});
		}
		dp[SZ(v)]=dp[SZ(v)+1]={0,0};
		for(int i=SZ(v)-1;i>=0;i--){
			dp[i].F=max(dp[i+1].F,dp[i+2].S)+ral(v[i].F,v[i].S-1);
			dp[i].S=max(dp[i+1].S,dp[i+2].F)+cal(v[i].F-1,v[i].S);
		}
		ans+=max(dp[0].F,dp[0].S);
		for(auto x:v) t[x.F][x.S]=0;
	}
	cout<<ans;
	
	return 0;
}

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