Submission #920186

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

joi2019_ho_t3

#include<bits/stdc++.h>
#define int long long
#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;

vector<int>a,b,c;
vector<vector<vector<vector<int>>>>dp;

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=1e15;
	if(x!=a.size() && t!=1){
		int ind=upper_bound(all(b),a[x])-b.begin();
		ind=min(ind,y);
		int ind2=upper_bound(all(c),a[x])-c.begin();
		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=upper_bound(all(a),b[y])-a.begin();
		ind=min(ind,x);
		int ind2=upper_bound(all(c),b[y])-c.begin();
		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=upper_bound(all(a),c[z])-a.begin();
		ind=min(ind,x);
		int ind2=upper_bound(all(b),c[z])-b.begin();
		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);
		}
	}
	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,1);
	if(ans==1e15)cout<<-1<<endl;
	else cout<<ans<<endl;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'long long int f(long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:16:6: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  if(z!=c.size() && t!=3){
      |     ~^~~~~~~~~~

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