Submission #1220663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220663		boclobanchat	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	15 / 100	39 ms	2348 KiB

joi2019_ho_t3

#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;
}

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