제출 #542355

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542355		codr0	즐거운 채소 기르기 (JOI14_growing)	C++14	0 / 100	2 ms	3284 KiB

growing

// Code by Parsa Eslami

#include <bits/stdc++.h>
#define pii pair<int,int>
#define bit(i,j) ((j>>i)&1)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';

using namespace std;

	void Main(){
		int n; cin>>n;
		string s;
		cin>>s; s='$'+s;
		int r(0),g(0),y(0);
		int R[n+1],G[n+1],Y[n+1];
		int indr[n+1],indg[n+1],indy[n+1];
		FOR(i,1,n){
			if(s[i]=='R'){
				r++;
				indr[r]=i;
			}else if(s[i]=='Y'){
				y++;
				indy[y]=i;
			}else{
				g++;
				indg[g]=i;
			}
			R[i]=r;
			G[i]=g;
			Y[i]=y;
		}
		int dp[r+1][g+1][y+1][3];
		FOR(i,0,r) FOR(j,0,g) FOR(w,0,y) FOR(x0,0,2) dp[i][j][w][x0]=1e9;
		if(r!=0) dp[1][0][0][0]=0;
		if(y!=0) dp[0][0][1][2]=0;
		if(g!=0) dp[0][1][0][1]=0;
		FOR(s,1,n){
			FOR(i,0,min(s,r)) FOR(j,0,min(s-i,g)){
				int w=s-i-j;
				if(w>y) continue;
				if(i!=r){
					dp[i+1][j][w][0]=min(min(dp[i][j][w][1],dp[i][j][w][2])+max(0,j-G[indr[i+1]])+max(0,w-Y[indr[i+1]]),dp[i+1][j][w][0]);
				}
				if(j!=g){
					dp[i][j+1][w][1]=min(min(dp[i][j][w][0],dp[i][j][w][2])+max(0,i-R[indg[j+1]])+max(0,w-Y[indg[j+1]]),dp[i][j+1][w][1]);
				}
				if(w!=y){
					dp[i][j][w+1][2]=min(min(dp[i][j][w][1],dp[i][j][w][0])+max(0,j-G[indy[w+1]])+max(0,i-R[indy[w+1]]),dp[i][j][w+1][2]);
				}
			}
		}
		int ans=min(dp[r][g][y][0],dp[r][g][y][1]);
		ans=min(ans,dp[r][g][y][2]);
		if(ans==1e9) cout<<"-1\n";
		else cout<<ans<<'\n';
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);

	int T=1;
	while(T--) Main();

	return 0;
	}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55