Submission #821730

#	Time	Username	Problem	Language	Result	Execution time	Memory
821730		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	404 ms	1025684 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
//#define int long long
//#define ld long double
using namespace std;
using ll=long long;
const int inf = 1e9;
const int MN =400+5;
const int mod=1e9+7;
int n;
string s;
int cnt[MN][MN][4][4];
int dp[MN][MN][MN][4];
int a[MN],b[MN],c[MN];
void solve() {
	cin>>n>>s;
//	s="#"+s;
	int n1=0,n2=0,n3=0;
	for (int i=0; i<n; i++) {
		if(s[i]=='R') a[++n1]=i;
		else if(s[i]=='Y') b[++n2]=i;
		else c[++n3]=i;
	}
	int k;
	k=0;
	for (int i=1; i<=n1; i++) {
		k=0;
		for (int j=1; j<=n2; j++) {
			if(b[j]>a[i]) k++;
			cnt[i][j][1][2]=k;
//			cout<<cnt[i][j][1][2]<<" ";
		}
	}
	k=0;
	for (int i=1; i<=n1; i++) {
		k=0;
		for (int j=1; j<=n3; j++) {
			if(c[j]>a[i]) k++;
			cnt[i][j][1][3]=k;
		}
	}
	k=0;
	for (int i=1; i<=n2; i++) {
		k=0;
		for (int j=1; j<=n1; j++) {
			if(a[j]>b[i]) k++;
			cnt[i][j][2][1]=k;
		}
	}
	k=0;
	for (int i=1; i<=n2; i++) {
		k=0;
		for (int j=1; j<=n3; j++) {
			if(c[j]>b[i]) k++;
			cnt[i][j][2][3]=k;
		}
	}
	k=0;
	for (int i=1; i<=n3; i++) {
		k=0;
		for (int j=1; j<=n1; j++) {
			if(a[j]>c[i]) k++;
			cnt[i][j][3][1]=k;
		}
	}
	k=0;
	for (int i=1; i<=n3; i++) {
		k=0;
		for (int j=1; j<=n2; j++) {
			if(b[j]>c[i]) k++;
			cnt[i][j][3][2]=k;
		}
	}
	for (int i=0; i<=n; i++) {
		for (int j=0; j<=n; j++) {
			for (int l=0; l<=n; l++) {
				dp[i][j][l][1]=dp[i][j][l][2]=dp[i][j][l][3]=inf;
			}
		}
	}
	dp[0][0][0][1]=dp[0][0][0][2]=dp[0][0][0][3]=0;
	for (int i=0; i<=n1; i++) {
		for (int j=0; j<=n2; j++) {
			for (int l=0; l<=n3; l++) {
				if(i>0) dp[i][j][l][1] = min(dp[i-1][j][l][2],dp[i-1][j][l][3]) + cnt[i][j][1][2] + cnt[i][l][1][3];
				if(j>0) dp[i][j][l][2] = min(dp[i][j-1][l][1],dp[i][j-1][l][3]) + cnt[j][i][2][1] + cnt[j][l][2][3];
				if(l>0) dp[i][j][l][3] = min(dp[i][j][l-1][2],dp[i][j][l-1][1]) + cnt[l][i][3][1] + cnt[l][j][3][2];
			}
		}
	}
	int ans=min({dp[n1][n2][n3][1], dp[n1][n2][n3][2], dp[n1][n2][n3][3]});
	if(ans>=inf) cout<<-1;
	else cout<<ans;
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
//	freopen(".inp", "r", stdin);
//	freopen(".out", "w", stdout);
	int t=1;
//	cin>>t;
	while(t--) {
		solve();
	}
		
}

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25