oj.uz

Submission #1114409

# Submission time Handle Problem Language Result Execution time Memory
1114409 2024-11-18T20:04:13 Z elotelo966 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster 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 lim 405
#define fi first
#define se second

int n;

string s;

vector<int> r,y,g;

int dp[lim][lim][lim][3];

//0->red
//1->yellow
//2->green

inline int f(int sira,int red,int yel,int gre,int eski){
	//cout<<sira<<" "<<red<<" "<<yel<<" "<<gre<<" "<<eski<<endl;
	if(sira>n)return 0;
	if(~dp[red][yel][gre][eski])return dp[red][yel][gre][eski];
	int cev=INT_MAX;
	if((sira==1 || eski!=0) && red!=r.size()){
		cev=min(cev,f(sira+1,red+1,yel,gre,0)+((f(sira+1,red+1,yel,gre,0)==INT_MAX)?0:abs(sira-r[red])));
	}
	if(eski!=1 && yel!=y.size()){
		cev=min(cev,f(sira+1,red,yel+1,gre,1)+((f(sira+1,red,yel+1,gre,1)==INT_MAX)?0:abs(sira-y[yel])));
	}
	if(eski!=2 && gre!=g.size()){
		cev=min(cev,f(sira+1,red,yel,gre+1,2)+((f(sira+1,red,yel,gre+1,2)==INT_MAX)?0:abs(sira-g[gre])));
	}
	return dp[red][yel][gre][eski]=cev;
}

int32_t main(){
	faster
	cin>>n;
	cin>>s;
	
	FOR{
		if(s[i-1]=='R')r.push_back(i);
		else if(s[i-1]=='Y')y.push_back(i);
		else g.push_back(i);
	}
	
	memset(dp,-1,sizeof(dp));
	
	int cev=f(1,0,0,0,0);
	
	if(cev==INT_MAX)cout<<-1<<'\n';
	else cout<<cev/2<<'\n';
	
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'long long int f(long long int, long long int, long long int, long long int, long long int)':
joi2019_ho_t3.cpp:31:32: 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]
   31 |  if((sira==1 || eski!=0) && red!=r.size()){
      |                             ~~~^~~~~~~~~~
joi2019_ho_t3.cpp:34:19: 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]
   34 |  if(eski!=1 && yel!=y.size()){
      |                ~~~^~~~~~~~~~
joi2019_ho_t3.cpp:37:19: 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]
   37 |  if(eski!=2 && gre!=g.size()){
      |                ~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 850 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 850 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 767 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 850 ms 1048576 KB Time limit exceeded
2 Halted 0 ms 0 KB -