Submission #920193

#	Time	Username	Problem	Language	Result	Execution time	Memory
920193		ihceker	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	291 ms	147028 KiB

joi2019_ho_t3

#include<bits/stdc++.h>
#define MOD 1000000007
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

int pre[405][2],pre2[405][2],pre3[405][2];
vector<int>a,b,c;
vector<vector<vector<vector<int>>>>dp;

inline int f(int x,int y,int z,int t){
	if(x==a.size() && y==b.size() && z==c.size())return 0;
	if(dp[x][y][z][t]!=-1)return dp[x][y][z][t];
	int mn=1e9;
	if(x!=a.size() && t!=1){
		int ind=pre[x][0];
		ind=min(ind,y);
		int ind2=pre[x][1];
		ind2=min(ind2,z);
		mn=min(mn,f(x+1,y,z,1)+y-ind+z-ind2);
	}
	if(y!=b.size() && t!=2){
		int ind=pre2[y][0];
		ind=min(ind,x);
		int ind2=pre2[y][1];
		ind2=min(ind2,z);
		mn=min(mn,f(x,y+1,z,2)+x-ind+z-ind2);
	}
	if(z!=c.size() && t!=3){
		int ind=pre3[z][0];
		ind=min(ind,x);
		int ind2=pre3[z][1];
		ind2=min(ind2,y);
		mn=min(mn,f(x,y,z+1,3)+x-ind+y-ind2);
	}
	return dp[x][y][z][t]=mn;
}

int32_t main(){
	fast;
	int n;
	cin>>n;
	string s;
	cin>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='R'){
			a.pb(i);
		}
		if(s[i]=='G'){
			b.pb(i);
		}
		if(s[i]=='Y'){
			c.pb(i);
		}
	}
	for(int i=0;i<a.size();i++){
		pre[i][0]=upper_bound(all(b),a[i])-b.begin();
		pre[i][1]=upper_bound(all(c),a[i])-c.begin();
	}
	for(int i=0;i<b.size();i++){
		pre2[i][0]=upper_bound(all(a),b[i])-a.begin();
		pre2[i][1]=upper_bound(all(c),b[i])-c.begin();
	}
	for(int i=0;i<c.size();i++){
		pre3[i][0]=upper_bound(all(a),c[i])-a.begin();
		pre3[i][1]=upper_bound(all(b),c[i])-b.begin();
	}
	dp.assign((int)a.size()+5,vector<vector<vector<int>>>((int)b.size()+5,vector<vector<int>>((int)c.size()+5,vector<int>(4,-1))));
	int ans=f(0,0,0,0);
	if(ans==1e9)cout<<-1<<endl;
	else cout<<ans<<endl;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:16:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if(x==a.size() && y==b.size() && z==c.size())return 0;
      |     ~^~~~~~~~~~
joi2019_ho_t3.cpp:16:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if(x==a.size() && y==b.size() && z==c.size())return 0;
      |                    ~^~~~~~~~~~
joi2019_ho_t3.cpp:16:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if(x==a.size() && y==b.size() && z==c.size())return 0;
      |                                   ~^~~~~~~~~~
joi2019_ho_t3.cpp:19:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  if(x!=a.size() && t!=1){
      |     ~^~~~~~~~~~
joi2019_ho_t3.cpp:26:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if(y!=b.size() && t!=2){
      |     ~^~~~~~~~~~
joi2019_ho_t3.cpp:33:6: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(z!=c.size() && t!=3){
      |     ~^~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int32_t main()':
joi2019_ho_t3.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
joi2019_ho_t3.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=0;i<b.size();i++){
      |              ~^~~~~~~~~
joi2019_ho_t3.cpp:68:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i=0;i<c.size();i++){
      |              ~^~~~~~~~~

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