oj.uz

Submission #922297

# Submission time Handle Problem Language Result Execution time Memory
922297 2024-02-05T11:34:32 Z elotelo966 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 21 ms 140380 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 mid (start+end)/2
#define lim 65
#define fi first
#define se second
int n;// 1 2 3
int cev=LLONG_MAX;
vector<int> v[4];
int dp[lim][lim][lim][lim];

inline void dpp(int red,int gre,int yel,int sira,int renk,int tut,string st){
	//cout<<red<<" "<<gre<<" "<<yel<<" "<<sira<<" "<<tut<<" "<<renk<<" "<<st+'Y'<<endl;
	if(red==v[1].size() && gre==v[2].size() && yel==v[3].size()){
		//return tut;
		cev=min(cev,tut);
		return ;
	}
	//if(~dp[sira][red][gre][yel])return dp[sira][red][gre][yel];
	int yum=LLONG_MAX;
	if(renk!=1 && red<v[1].size()){
		//cout<<"r"<<red<<" "<<gre<<" "<<yel<<" "<<sira<<" "<<tut<<" "<<abs(v[1][red]-sira)<<" "<<st+'R'<<endl;
		//yum=min(yum,dpp(red+1,gre,yel,sira+1,1,tut+abs(v[1][red]-sira),st+'R'));
		dpp(red+1,gre,yel,sira+1,1,tut+abs(v[1][red]-sira),st+'R');
	}
	if(renk!=2 && gre<v[2].size()){
		//cout<<"g"<<red<<" "<<gre<<" "<<yel<<" "<<sira<<" "<<tut<<" "<<abs(v[2][gre]-sira)<<" "<<st+'G'<<endl;
		//yum=min(yum,dpp(red,gre+1,yel,sira+1,2,tut+abs(v[2][gre]-sira),st+'G'));	
		dpp(red,gre+1,yel,sira+1,2,tut+abs(v[2][gre]-sira),st+'G');
	}
	if(renk!=3 && yel<v[3].size()){
		//cout<<"y"<<red<<" "<<gre<<" "<<yel<<" "<<sira<<" "<<tut<<" "<<abs(v[3][yel]-sira)<<" "<<st+'Y'<<endl;
		//yum=min(yum,dpp(red,gre,yel+1,sira+1,3,tut+abs(v[3][yel]-sira),st+'Y'));
		dpp(red,gre,yel+1,sira+1,3,tut+abs(v[3][yel]-sira),st+'Y');
	}
	//return dp[sira][red][gre][yel]=yum;
}

int32_t main(){
	faster
	memset(dp,-1,sizeof(dp));
	cin>>n;
	string s;cin>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='R')v[1].push_back(i+1);
		else if(s[i]=='G')v[2].push_back(i+1);
		else v[3].push_back(i+1);
	}
	string h="";
	//cout<<dpp(0,0,0,1,0,0,h)<<'\n';
	dpp(0,0,0,1,0,0,h);
	if(cev==LLONG_MAX){
		cev=-2;
	}
	cout<<cev/2<<'\n';
	return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'void dpp(long long int, long long int, long long int, long long int, long long int, long long int, std::string)':
joi2019_ho_t3.cpp:18:8: 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]
   18 |  if(red==v[1].size() && gre==v[2].size() && yel==v[3].size()){
      |     ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:18:28: 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]
   18 |  if(red==v[1].size() && gre==v[2].size() && yel==v[3].size()){
      |                         ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:18:48: 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]
   18 |  if(red==v[1].size() && gre==v[2].size() && yel==v[3].size()){
      |                                             ~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:25: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]
   25 |  if(renk!=1 && red<v[1].size()){
      |                ~~~^~~~~~~~~~~~
joi2019_ho_t3.cpp:30: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]
   30 |  if(renk!=2 && gre<v[2].size()){
      |                ~~~^~~~~~~~~~~~
joi2019_ho_t3.cpp:35: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]
   35 |  if(renk!=3 && yel<v[3].size()){
      |                ~~~^~~~~~~~~~~~
joi2019_ho_t3.cpp:24:6: warning: unused variable 'yum' [-Wunused-variable]
   24 |  int yum=LLONG_MAX;
      |      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 140124 KB Output is correct
2 Correct 18 ms 140116 KB Output is correct
3 Correct 21 ms 140268 KB Output is correct
4 Correct 20 ms 140120 KB Output is correct
5 Correct 20 ms 140124 KB Output is correct
6 Correct 20 ms 140124 KB Output is correct
7 Correct 20 ms 140124 KB Output is correct
8 Correct 20 ms 140124 KB Output is correct
9 Correct 20 ms 140036 KB Output is correct
10 Correct 21 ms 140060 KB Output is correct
11 Incorrect 21 ms 140124 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 140124 KB Output is correct
2 Correct 18 ms 140116 KB Output is correct
3 Correct 21 ms 140268 KB Output is correct
4 Correct 20 ms 140120 KB Output is correct
5 Correct 20 ms 140124 KB Output is correct
6 Correct 20 ms 140124 KB Output is correct
7 Correct 20 ms 140124 KB Output is correct
8 Correct 20 ms 140124 KB Output is correct
9 Correct 20 ms 140036 KB Output is correct
10 Correct 21 ms 140060 KB Output is correct
11 Incorrect 21 ms 140124 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 140192 KB Output is correct
2 Correct 19 ms 140380 KB Output is correct
3 Correct 18 ms 140228 KB Output is correct
4 Correct 18 ms 140168 KB Output is correct
5 Correct 20 ms 140376 KB Output is correct
6 Correct 19 ms 140380 KB Output is correct
7 Correct 20 ms 140380 KB Output is correct
8 Correct 19 ms 140192 KB Output is correct
9 Correct 20 ms 140380 KB Output is correct
10 Correct 21 ms 140376 KB Output is correct
11 Correct 20 ms 140380 KB Output is correct
12 Correct 20 ms 140184 KB Output is correct
13 Correct 19 ms 140200 KB Output is correct
14 Correct 20 ms 140124 KB Output is correct
15 Correct 19 ms 140380 KB Output is correct
16 Correct 20 ms 140380 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 140124 KB Output is correct
2 Correct 18 ms 140116 KB Output is correct
3 Correct 21 ms 140268 KB Output is correct
4 Correct 20 ms 140120 KB Output is correct
5 Correct 20 ms 140124 KB Output is correct
6 Correct 20 ms 140124 KB Output is correct
7 Correct 20 ms 140124 KB Output is correct
8 Correct 20 ms 140124 KB Output is correct
9 Correct 20 ms 140036 KB Output is correct
10 Correct 21 ms 140060 KB Output is correct
11 Incorrect 21 ms 140124 KB Output isn't correct
12 Halted 0 ms 0 KB -