oj.uz

Submission #1114410

# Submission time Handle Problem Language Result Execution time Memory
1114410 2024-11-18T20:06:59 Z elotelo966 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 780428 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 'int f(int, int, int, int, int)':
joi2019_ho_t3.cpp:31:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<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: 'int' and 'std::vector<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: 'int' and 'std::vector<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 Correct 498 ms 780412 KB Output is correct
2 Correct 466 ms 780360 KB Output is correct
3 Correct 474 ms 780360 KB Output is correct
4 Correct 484 ms 780204 KB Output is correct
5 Correct 489 ms 780364 KB Output is correct
6 Correct 486 ms 780360 KB Output is correct
7 Correct 484 ms 780308 KB Output is correct
8 Correct 488 ms 780360 KB Output is correct
9 Correct 476 ms 780360 KB Output is correct
10 Correct 483 ms 780224 KB Output is correct
11 Incorrect 486 ms 780220 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 780412 KB Output is correct
2 Correct 466 ms 780360 KB Output is correct
3 Correct 474 ms 780360 KB Output is correct
4 Correct 484 ms 780204 KB Output is correct
5 Correct 489 ms 780364 KB Output is correct
6 Correct 486 ms 780360 KB Output is correct
7 Correct 484 ms 780308 KB Output is correct
8 Correct 488 ms 780360 KB Output is correct
9 Correct 476 ms 780360 KB Output is correct
10 Correct 483 ms 780224 KB Output is correct
11 Incorrect 486 ms 780220 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 780240 KB Output is correct
2 Correct 470 ms 780380 KB Output is correct
3 Correct 482 ms 780296 KB Output is correct
4 Correct 495 ms 780428 KB Output is correct
5 Correct 489 ms 780360 KB Output is correct
6 Correct 472 ms 780412 KB Output is correct
7 Correct 453 ms 780360 KB Output is correct
8 Correct 439 ms 780248 KB Output is correct
9 Correct 463 ms 780360 KB Output is correct
10 Correct 465 ms 780404 KB Output is correct
11 Correct 475 ms 780360 KB Output is correct
12 Execution timed out 501 ms 780360 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 780412 KB Output is correct
2 Correct 466 ms 780360 KB Output is correct
3 Correct 474 ms 780360 KB Output is correct
4 Correct 484 ms 780204 KB Output is correct
5 Correct 489 ms 780364 KB Output is correct
6 Correct 486 ms 780360 KB Output is correct
7 Correct 484 ms 780308 KB Output is correct
8 Correct 488 ms 780360 KB Output is correct
9 Correct 476 ms 780360 KB Output is correct
10 Correct 483 ms 780224 KB Output is correct
11 Incorrect 486 ms 780220 KB Output isn't correct
12 Halted 0 ms 0 KB -