Submission #1089453

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

joi2019_ho_t3

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 401;

using namespace std;
using namespace __gnu_pbds;

ll n, m, dp[N][N][N][3], pr[N][3], a, b, c;
vector <ll> v[3];
string s;

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	cin >> s;
	s = " " + s;
	for (int i = 1; i <= n; i++){
		pr[i][0] = pr[i - 1][0];
		pr[i][1] = pr[i - 1][1];
		pr[i][2] = pr[i - 1][2];
		if (s[i] == 'R'){
			pr[i][0]++;
			v[0].pb(i);
			a++;
		}
		else if (s[i] == 'Y'){
			pr[i][1]++;
			v[1].pb(i);
			b++;
		}
		else{
			pr[i][2]++;
			v[2].pb(i);
			c++;
		}
	}
	for (int i = 0; i <= n; i++){
		for (int r = 0; r <= a; r++){
			for (int y = 0; y <= b; y++){
				dp[i][r][y][0] = 1e10;
				dp[i][r][y][1] = 1e10;
				dp[i][r][y][2] = 1e10;
			}
		}
	}
	dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
	for (int i = 1; i <= n; i++){
		for (int r = 0; r <= a; r++){
			for (int y = 0; y <= b; y++){
				ll g = i - r - y;
				if (r + y > i){
					break;
				}
				if(g>c)continue;
				if (r > 0){
					ll pos = v[0][r - 1];
					ll cnt = max(0ll,y - pr[pos][1]) + max(0ll,g - pr[pos][2]);
					dp[i][r][y][0] = min (dp[i - 1][r - 1][y][1], dp[i - 1][r - 1][y][2]) + max (0ll, pos + cnt - i);
				}
				if (y > 0){
					ll pos = v[1][y - 1];
					ll cnt = max(0ll,r - pr[pos][0]) + max(0ll,g - pr[pos][2]);
					dp[i][r][y][1] = min (dp[i - 1][r][y - 1][0], dp[i - 1][r][y - 1][2]) + max (0ll, pos + cnt - i);
				}
				if (g > 0){
					ll pos = v[2][g - 1];
					ll cnt = max(0ll,y - pr[pos][1]) + max(0ll,r - pr[pos][0]);
					dp[i][r][y][2] = min (dp[i - 1][r][y][1], dp[i - 1][r][y][0]) + max (0ll, pos + cnt - i);
				}
			}
		}
	}
	ll ali = min ({dp[n][a][b][0], dp[n][a][b][1], dp[n][a][b][2]});
	cout << ( ali >= 1e10 ? -1 : ali );
}

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