Submission #1220919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220919		boclobanchat	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	54 ms	4932 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int dp[2][404][404][3],pos[404][3],pref[404][404][3][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=0;i<=cnta;i++) for(int j=1;j<=cntb;j++)
	{
//		pref[i][j][0][1]=pref[i][j-1][0][1];
		for(int k=1;k<=i;k++) if(pos[k][0]>pos[j][1]) pref[i][j][0][1]++;
	}
	for(int i=0;i<=cnta;i++) for(int j=1;j<=cntc;j++)
	{
//		pref[i][j][0][2]=pref[i][j-1][0][2];
		for(int k=1;k<=i;k++) if(pos[k][0]>pos[j][2]) pref[i][j][0][2]++;
	}
	for(int i=0;i<=cntb;i++) for(int j=1;j<=cnta;j++)
	{
//		pref[i][j][1][0]=pref[i][j-1][1][0];
		for(int k=1;k<=i;k++) if(pos[k][1]>pos[j][0]) pref[i][j][1][0]++;
	}
	for(int i=0;i<=cntb;i++) for(int j=1;j<=cntc;j++)
	{
//		pref[i][j][1][2]=pref[i][j-1][1][2];
		for(int k=1;k<=i;k++) if(pos[k][1]>pos[j][2]) pref[i][j][1][2]++;
	}
	for(int i=0;i<=cntc;i++) for(int j=1;j<=cnta;j++)
	{
//		pref[i][j][2][0]=pref[i][j-1][2][0];
		for(int k=1;k<=i;k++) if(pos[k][2]>pos[j][0]) pref[i][j][2][0]++;
	}
	for(int i=0;i<=cntc;i++) for(int j=1;j<=cntb;j++)
	{
//		pref[i][j][2][1]=pref[i][j-1][2][1];
		for(int k=1;k<=i;k++) if(pos[k][2]>pos[j][1]) pref[i][j][2][1]++;
	}
    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[a][j][k][0],min(dp[b][j-1][k][1],dp[b][j-1][k][2])+pref[k][j][1][0]+pref[i-j-k][j][2][0]);
    		if(k>0) dp[a][j][k][1]=min(dp[a][j][k][1],min(dp[b][j][k-1][0],dp[b][j][k-1][2])+pref[j][k][0][1]+pref[i-j-k][k][2][1]);
    		if(j+k<i&&i-j-k<=cntc) dp[a][j][k][2]=min(dp[a][j][k][2],min(dp[b][j][k][0],dp[b][j][k][1])+pref[j][i-j-k][0][2]+pref[k][i-j-k][1][2]);
		}
	}
	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;
}

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