제출 #1317788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317788		JuanJL	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	60 / 100	318 ms	699060 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define forn(i,a,b) for(int i = a; i<b; i++)
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
typedef long long ll;

string opc = "RGY";

ll dp[65][5][65][65][65];

ll n;
string s;
vector<vector<ll>> pos(3);
map<char,ll> ri;

ll select(ll k , ll R, ll G, ll Y){
	if(k==0) return R;
	if(k==1) return G;
	if(k==2) return Y;
}

ll f(ll x, ll ant, ll R, ll G, ll Y){
	
	ll &res = dp[x][ant][R][G][Y];
	if(res!=-1) return res;
	if(x==n) return 0;

	res = 10000000000;
	forn(k,0,3){
		if(k==ant) continue;
		
		ll rgy = select(k,R,G,Y);
		if(rgy==SZ(pos[k])) continue;

		
		ll cost = 0;
		ll j = pos[k][rgy];
		forn(h,0,3){
			ll mrgy = select(h,R,G,Y);
			cost += max((ll)0,(lower_bound(ALL(pos[h]),j)-pos[h].begin()) - mrgy);
		}

		ll nR = R; if(k==0) nR++;
		ll nG = G; if(k==1) nG++;
		ll nY = Y; if(k==2) nY++;
		
		res=min(res, f(x+1,k,nR,nG,nY)+cost);
	}
	//cout<<x<<" "<<R<<" "<<G<<" "<<Y<<"-------> "<<res<<'\n';
	return res;
}
int main(){ FIN;
	cin>>n;
	cin>>s;

	ri['R']=0;
	ri['G']=1;
	ri['Y']=2;

	forn(i,0,n) pos[ri[s[i]]].pb(i);

	mset(dp,-1);

	ll res=f(0,4,0,0,0);

	if(res>1000000000) cout<<"-1"<<'\n';
	else cout<<res<<'\n';
	
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp: In function 'll select(ll, ll, ll, ll)':
joi2019_ho_t3.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^

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