Submission #98919

#	Time	Username	Problem	Language	Result	Execution time	Memory
98919		MvC	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++11	100 / 100	134 ms	163100 KiB

joi2019_ho_t3

#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,nr[3],f[405][405][405][3],r,g,y,R,G,Y,s;
vector<pair<int,pair<int,int> > >v[3];
char c;
int get(char c)
{
	if(c=='R')return 0;
	if(c=='G')return 1;
	return 2;
}
int cst(pair<int,pair<int,int> >x,pair<int,pair<int,int> >y)
{
	return abs(x.fr-y.fr)+abs(x.sc.fr-y.sc.fr)+abs(x.sc.sc-y.sc.sc);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>c;
		nr[get(c)]++;
		v[get(c)].pb({nr[0],{nr[1],nr[2]}});
	}
	R=v[0].size(),G=v[1].size(),Y=v[2].size();
	if(max(max(R,G),Y)>(n+1)/2)rc(-1);
	for(r=0;r<=R;r++)
	{
		for(g=0;g<=G;g++)
		{
			for(y=0;y<=Y;y++)
			{
				s=r+g+y;
				if(!s)continue;
				f[r][g][y][0]=f[r][g][y][1]=f[r][g][y][2]=inf;
				if(r)
				{
					f[r][g][y][0]=min(f[r-1][g][y][1],f[r-1][g][y][2])+cst(v[0][r-1],{r,{g,y}});
				}
				if(g)
				{
					f[r][g][y][1]=min(f[r][g-1][y][0],f[r][g-1][y][2])+cst(v[1][g-1],{r,{g,y}});
				}
				if(y)
				{
					f[r][g][y][2]=min(f[r][g][y-1][0],f[r][g][y-1][1])+cst(v[2][y-1],{r,{g,y}});
				}
			}
		}
	}
	cout<<min(min(f[R][G][Y][0],f[R][G][Y][1]),f[R][G][Y][2])/2<<endl;
    return 0;
}

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