제출 #1220663

#제출 시각아이디문제언어결과실행 시간메모리
1220663boclobanchatGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
15 / 100
39 ms2348 KiB
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int dp[2][404][404][3],pos[404][3];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin>>n>>s;
    s=' '+s;
    int cnta=0,cntb=0,cntc=0;
    for(int i=1;i<=n;i++)
    {
    	if(s[i]=='R') pos[++cnta][0]=i;
    	if(s[i]=='G') pos[++cntb][1]=i;
    	if(s[i]=='Y') pos[++cntc][2]=i;
	}
    for(int i=1;i<=n;i++)
    {
    	int a=i%2,b=1-a;
    	for(int j=0;j<=i&&j<=cnta;j++) for(int k=0;k+j<=i&&k<=cntb;k++)
    	{
    		dp[a][j][k][0]=dp[a][j][k][1]=dp[a][j][k][2]=INF;
    		if(j>0) dp[a][j][k][0]=min(dp[b][j-1][k][1],dp[b][j-1][k][2])+abs(pos[j][0]-i);
    		if(k>0) dp[a][j][k][1]=min(dp[b][j][k-1][0],dp[b][j][k-1][2])+abs(pos[k][1]-i);
    		if(j+k<i&&i-j-k<=cntc) dp[a][j][k][2]=min(dp[b][j][k][0],dp[b][j][k][1])+abs(pos[i-j-k][2]-i);
		}
	}
	int ans=min(dp[n%2][cnta][cntb][0],min(dp[n%2][cnta][cntb][1],dp[n%2][cnta][cntb][2]));
	if(ans>=INF) cout<<-1;
	else cout<<ans/2;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...