Submission #707023

#	Time	Username	Problem	Language	Result	Execution time	Memory
707023		blacktulip	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	21 ms	35532 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo; 
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
 
const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 400;
const lo mod = 1000000007;
 
int n,m,k,flag,t,x,siz1,siz2,siz3;
int cev;
unordered_map<int,long long>dp[li][li][4];
string s;
vector<int> v[3];
 
inline int in(){
    int x;
    scanf("%d",&x);
    return x;
}

inline long long f(int bir,int iki,int uc,int sira,int son){
	long long cevv=100000000000000000;
	if(bir==siz1 && iki==siz2 && uc==siz3)return 0;
	if(dp[bir][iki][son].find(uc)!=dp[bir][iki][son].end())return dp[bir][iki][son][uc];
	if(bir!=siz1){
		if(son!=0)cevv=min(cevv,f(bir+1,iki,uc,sira+1,0)+abs(v[0][bir]-sira));
	}
	if(iki!=siz2){
		if(son!=1)cevv=min(cevv,f(bir,iki+1,uc,sira+1,1)+abs(v[1][iki]-sira));
	}
	if(uc!=siz3){
		if(son!=2)cevv=min(cevv,f(bir,iki,uc+1,sira+1,2)+abs(v[2][uc]-sira));
	}
	return dp[bir][iki][son][uc]=cevv;
}

int main(void){
    fio();
    cin>>n;
    cin>>s;
    for(int i=0;i<n;i++){
		if(s[i]=='R'){s[i]='a';siz1++;}
		if(s[i]=='G'){s[i]='b';siz2++;}
		if(s[i]=='Y'){s[i]='c';siz3++;}
		v[s[i]-'a'].pb(i);
	}
	long long yaz=f(0,0,0,0,3);
	if(yaz>=100000000000000000)yaz=-2;
	cout<<yaz/2;
    return 0;
}

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