Submission #487370

#	Time	Username	Problem	Language	Result	Execution time	Memory
487370		PoPularPlusPlus	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	0 ms	204 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pb(e) push_back(e)
#define sv(a) sort(a.begin(),a.end())
#define sa(a,n) sort(a,a+n)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
#define ar array
#define all(x) x.begin(),x.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007; 
const double PI=3.14159265358979323846264338327950288419716939937510582097494459230;
bool remender(ll a , ll b){return a%b;}

//ll dp[401][401][401][3];
vector<vector<vector<vector<int>>>> dp;
vector<int> a , b , c;

vector<pair<int,int>> up , up1 , up2;

ll rec(int i , int j , int k , int col , int s1 , int s2 , int s3){
	if(i == s1 && j == s2 && k == s3)return 0;
	if(dp[i][j][k][col]!=-1)return dp[i][j][k][col];
	if(col == 0){
		if(i == s1)return 1e9;
		int p = up[i].vf;
		p = max(0 , j - p);
		int p1 = up[i].vs;
		p1 = max(0 , k - p1);
		int pos = a[i] + p + p1;
		return dp[i][j][k][col] = (ll)abs(pos - (i + j + k)) + min(rec(i + 1 , j , k , 1 , s1 , s2 , s3) , rec(i + 1 , j , k , 2 , s1 , s2 , s3));
	}
	if(col == 1){
		if(j == s2)return 1e9;
		int p = up1[i].vf;
		p = max(0 , i - p);
		int p1 = up1[i].vs;
		p1 = max(0 , k - p1);
		int pos = b[j] + p + p1;
		return dp[i][j][k][col] = (ll)abs(pos - (i + j + k)) + min(rec(i , j + 1 , k , 0 ,  s1, s2 , s3) , rec(i , j + 1 , k , 2 , s1 , s2 , s3));
	}
	if(k == s3)return 1e9;
	int p = up2[i].vf;
	p = max(0 , i - p);
	int p1 = up2[i].vs;
	p1 = max(0 , j - p1);
	int pos = c[k] + p + p1;
	return dp[i][j][k][col] = (ll)abs(pos - (i + j + k)) + min(rec(i , j , k + 1 , 0 ,s1 , s2 ,s3) , rec(i , j , k + 1 , 1 , s1 , s2 , s3));
}

void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	for(int i = 0; i < n; i++){
		if(s[i]=='R')a.pb(i);
		else if(s[i] == 'G')b.pb(i);
		else c.pb(i);
	}
	dp.resize(a.size() + 2);
	for(int i = 0; i < (int)a.size() + 1; i++){
		dp[i].resize(b.size() + 2);
		for(int j = 0; j < (int)b.size() + 1; j++){
			dp[i][j].resize(c.size() + 2);
			for(int k = 0; k < (int)c.size() + 1; k++){
				dp[i][j][k].pb(-1);
				dp[i][j][k].pb(-1);
				dp[i][j][k].pb(-1);
			}
		}
	}
	up.resize(a.size() + 2);
	up1.resize(b.size() + 2);
	up2.resize(c.size() + 2);
	for(int i = 0; i < (int)a.size(); i++){
		int p = upper_bound(all(b) , a[i]) - b.begin();
		int p1 = upper_bound(all(c) , a[i]) - c.begin();
		up[i] = mp(p,p1);
	}
	for(int i = 0; i < (int)b.size(); i++){
		int p = upper_bound(all(a) , b[i]) - a.begin();
		int p1 = upper_bound(all(c) , b[i]) - c.begin();
		up1[i] = mp(p,p1);
	}
	for(int i = 0; i < (int)c.size(); i++){
		int p = upper_bound(all(a) , c[i]) - a.begin();
		int p1 = upper_bound(all(b) , c[i]) - b.begin();
		up2[i] = mp(p,p1);
	}
	ll ans = min({rec(0,0,0,0,a.size(),b.size(),c.size()),rec(0,0,0,1,a.size(),b.size(),c.size()),rec(0,0,0,2,a.size(),b.size(),c.size())});
	if(ans >= 1e9)ans = -1;
	cout << ans << '\n';
	/*ll dp[a.size() + 1][b.size() + 1][c.size() + 1][3];
	ll ans = 1e9;
	for(int i = 0; i <= (int)a.size() + 1; i++){
		for(int j = 0; j <= (int)b.size() + 1; j++){
			for(int k = 0; k <= (int)c.size() + 1; k++){
				dp[i][j][k][2] = dp[i][j][k][1] = dp[i][j][k][0] = 1e9;
				if(k < (int)c.size()){
					int p = upper_bound(all(a) , c[k]) - a.begin();
					int p1 = upper_bound(all(b) , c[k]) - b.begin();
					int pos = c[k] + p + p1;
					dp[i][j][k][2] = min(dp[i][j][k][2] , abs(pos - (i + j + k)) + min(dp[i][j][k-1][0] , dp[i][j][k-1][1]));
				}
				if(j < (int)b.size()){
					int p = upper_bound(all(a) , b[j]) - a.begin();
					int p1 = upper_bound(all(c) , b[j]) - c.begin();
					int pos = b[j] + p + p1;
					dp[i][j][k][1] = min(dp[i][j][k][1] , abs(pos - (i + j + k)) + min(dp[i][j-1][k][0] , dp[i][j-1][k][2]));
				}
				if(i < (int)a.size()){
					int p = upper_bound(all(b) , a[i]) - b.begin();
					int p1 = upper_bound(all(c) , a[i]) - c.begin();
					int pos = a[i] + p + p1;
					dp[i][j][k][0] = min(dp[i][j][k][0] , abs(pos - (i + j + k)) + min(dp[i-1][j][k][1] , dp[i-1][j][k][2]));
				}
				if(a.size() + b.size() + c.size() == i + j + k + 1){
					ans = min({ans , dp[i][j][k][0] , dp[i][j][k][1] , dp[i][j][k][2]});
				}
			}
		}
	}
	cout << ans << '\n';*/
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
	//int t;cin >> t;while(t--)
	solve();
	return 0;
}

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