Submission #1128140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128140		armashka	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	65 ms	61000 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 2e6 + 5;
const ll M = 1e8;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            
 
ll n, r, g, y, pref[5][405], pos[5][405];
string s;
vector<vector<vector<vector<ll>>>> dp;
 
const void solve(/*Armashka*/) {
	cin >> n >> s;
	s = " " + s;
	for (int i = 1; i <= n; ++ i) {
		for (int j = 1; j <= 3; ++ j) pref[j][i] = pref[j][i - 1];
		if (s[i] == 'R') ++ pref[1][i], pos[1][++ r] = i;
		if (s[i] == 'G') ++ pref[2][i], pos[2][++ g] = i;
		if (s[i] == 'Y') ++ pref[3][i], pos[3][++ y] = i;
	}		
	dp.resize(4);
	for (int c = 1; c <= 3; ++ c) {
		dp[c].resize(r + 5);
		for (int i = 0; i <= r; ++ i) {
			dp[c][i].resize(g + 5);
			for (int j = 0; j <= g; ++ j) {
				dp[c][i][j].resize(y + 5);
				for (int k = 0; k <= y; ++ k) dp[c][i][j][k] = inf;
			}
		}
	}
	
	dp[1][0][0][0] = dp[2][0][0][0] = dp[3][0][0][0] = 0;
	for (int i = 0; i <= r; ++ i) {
		for (int j = 0; j <= g; ++ j) {
			for (int k = 0; k <= y; ++ k) {
				if (i) {
					ll x = max(0ll, pref[2][pos[1][i]] - j) + max(0ll, pref[3][pos[1][i]] - k);
					dp[1][i][j][k] = min({dp[1][i][j][k], dp[2][i - 1][j][k] + x, dp[3][i - 1][j][k] + x});
				}
				if (j) {
					ll x = max(0ll, pref[1][pos[2][j]] - i) + max(0ll, pref[3][pos[2][j]] - k);
					dp[2][i][j][k] = min({dp[2][i][j][k], dp[1][i][j - 1][k] + x, dp[3][i][j - 1][k] + x});
				}
				if (k) {
					ll x = max(0ll, pref[1][pos[3][k]] - i) + max(0ll, pref[2][pos[3][k]] - j);
					dp[3][i][j][k] = min({dp[3][i][j][k], dp[1][i][j][k - 1] + x, dp[2][i][j][k - 1] + x});
				}
			}
		}
	}
	ll ans = min({dp[1][r][g][y], dp[2][r][g][y], dp[3][r][g][y]});
	if (ans == inf) ans = -1;
	cout << ans << "\n";
}
            
signed main() {
    fast;
    //freopen("triangles.in", "r", stdin);
    //freopen("triangles.out", "w", stdout);
    int tt = 1;
	//cin >> tt;
    while (tt --) {                                                             
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/

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