Submission #816699

#	Time	Username	Problem	Language	Result	Execution time	Memory
816699		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	167 ms	97804 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
 
#pragma GCC optimize("O3")
#pragma GCC target("tune=native")
#pragma GCC optimize("unroll-loops")
 
using namespace std;
template<class A, class B>
ostream& operator<<(ostream& os, const pair<A, B> &p) {
  os << '(' << p.first << ',' << p.second << ')';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const vector<T> &v) {
  os << '{';
  bool osu = 1;
  for(auto &i : v) { if(!osu) os << ','; os << i; osu = 0; }
  os << '}';
  return os;
}
template<class T>
ostream& operator<<(ostream& os, const deque<T> &v) {
  os << '{';
  bool osu = 1;
  for(auto &i : v) { if(!osu) os << ','; os << i; osu = 0; }
  os << '}';
  return os;
}
template<class T,long long unsigned int size>
ostream& operator<<(ostream& os, const array<T,size> &arr) {
  os << '{';
  bool osu = 1;
  for(auto &i : arr) { if(!osu) os << ','; os << i; osu = 0; }
  os << '}';
  return os;
}
 
#define ll long long
#define ull unsigned long long
#define lll __int128
#define rep(i,n,N) for(int i=(n);i<=(N);++i)
#define For(i,n,N) for(int i=(n);i< (N);++i)
#define rap(i,n,N) for(int i=(n);i>=(N);--i)
#define rip(i,n,N,V) for(int i=(n);i<=(N);i+=V)
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
//#define le left
//#define ri right
#define fi first
#define se second
#define ff fi.fi
#define fs fi.se
#define sf se.fi
#define ss se.se
#define lc (id<<1)
#define rc ((id<<1)|1)
#define debug(x) cout << #x << " -> " << (x) << endl
#define out(x,y) cout << ">> " << (x) << " " << (y) << endl
#define ou3(x,y,z) cout << ">> " << (x) << " " << (y) << " " << (z) << endl
#define mems(x,y) memset(&x,y,sizeof x)
#define memsv(x,y) memset(&x[0], y, sizeof(x[0]) * x.size())
#define popcount __builtin_popcountll
#define clz(x) (1<<(31-__builtin_clz(x)))
#define clzll(x) (1LL<<(63-__builtin_clzll(x)))
#define all(x) x.begin(),x.end()
#define rsort(x) sort(x), reverse(x)
#define revsort(a,b) sort(a,b), reverse(a,b)
#define PQ(T) priority_queue<T>
#define PQr(T) priority_queue<T, vector<T>, greater<T>>
#define permute(x) while(next_permutation(all(x)))
#define distinct(x) x.erase(unique(all(x)),x.end())
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pii>
#define vll vector<ll>
#define vlll vector<pll>
#define vvll vector<vll>
#define ari(x) array<int,x>
#define arll(x) array<ll,x>
#define ard(x) array<double,x>
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define pllll pair<pll,pll>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define psi pair<string,int>
#define endl '\n'
const int MAX = 3e3+5;
const int MOD = 1000000007;
const ll MOD2 = 2010405347;
const ll INF = 2e18;
const int dr[]={1,-1,0,0,1,1,-1,-1};
const int dc[]={0,0,-1,1,1,-1,1,-1};
const double pi = acos(-1);
const double EPS = 1e-9;
const int block = 500;
inline ll pw(ll x,ll y,ll md=MOD){ll ret=1;x%=md;while(y){if(y&1)ret=ret*x%md;x=x*x%md,y>>=1;}return ret;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,cv[128],ans,dp[202][202][202][3],cs[3][3][202][202];
string s;
vi v[3];

int f(int a,int b,int c,int ls){
	if(a+b+c==n)return 0;
	int &ret = dp[a][b][c][ls];
	if(ret!=-1)return ret;
	ret = MOD;
	ari(3) z = {a,b,c};
	rep(i,0,2)if(i!=ls && z[i]!=v[i].size())ret = min(ret, f(a+(i==0), b+(i==1), c+(i==2), i) + cs[i][0][z[i]][a] + cs[i][1][z[i]][b] + cs[i][2][z[i]][c]);
	return ret;
}

int main(){
//	cout<<fixed<<setprecision(10);
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cv['R'] = 0;
	cv['G'] = 1;
	cv['Y'] = 2;
	cin>>n>>s;
	For(i,0,n)v[cv[s[i]]].pb(i);
	rep(i,0,2)if(v[i].size()>200)return cout<<"-1\n",0;
	ans = MOD;
	int nw;
	rep(i,0,2)rep(j,0,2)if(i!=j){
		For(a,0,v[j].size()){
			nw = a;
			For(b,0,v[i].size()){
				while(nw<v[j].size() && v[j][nw]<v[i][b])++nw;
				cs[i][j][b][a] = nw-a;
//				debug(vi({i,j,b,a,nw-a}));
			}
		}
	}
	mems(dp, -1);
	rep(i,0,2)if(v[i].size())ans = min(ans, f(i==0, i==1, i==2, i) + cs[i][0][0][0] + cs[i][1][0][0] + cs[i][2][0][0]);
	if(ans==MOD)ans = -1;
	cout<<ans<<endl;
	return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:114:28: warning: comparison of integer expressions of different signedness: 'std::array<int, 3>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |  rep(i,0,2)if(i!=ls && z[i]!=v[i].size())ret = min(ret, f(a+(i==0), b+(i==1), c+(i==2), i) + cs[i][0][z[i]][a] + cs[i][1][z[i]][b] + cs[i][2][z[i]][c]);
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:127:21: warning: array subscript has type 'char' [-Wchar-subscripts]
  127 |  For(i,0,n)v[cv[s[i]]].pb(i);
      |                     ^
joi2019_ho_t3.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 | #define For(i,n,N) for(int i=(n);i< (N);++i)
      |                                   ^
joi2019_ho_t3.cpp:132:3: note: in expansion of macro 'For'
  132 |   For(a,0,v[j].size()){
      |   ^~~
joi2019_ho_t3.cpp:42:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 | #define For(i,n,N) for(int i=(n);i< (N);++i)
      |                                   ^
joi2019_ho_t3.cpp:134:4: note: in expansion of macro 'For'
  134 |    For(b,0,v[i].size()){
      |    ^~~
joi2019_ho_t3.cpp:135:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  135 |     while(nw<v[j].size() && v[j][nw]<v[i][b])++nw;
      |           ~~^~~~~~~~~~~~

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