oj.uz

Submission #782182

# Submission time Handle Problem Language Result Execution time Memory
782182 2023-07-13T16:07:23 Z DangerNoodle7591 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
100 / 100
 336 ms 781704 KB 
#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define N 405
int n;
vector<int> red,green,yellow;
int tut[3][3][N][N];
int dp[N][N][N][3];
inline int hesap(int r,int g,int y,int son,int sira){
	if(sira>=n)return 0;
	if(dp[r][g][y][son]!=-1)return dp[r][g][y][son];
	int cev=1000000000;
	if((son!=0||r+g+y==0)&&r<red.size()){
		cev=min(cev,hesap(r+1,g,y,0,sira+1)+red[r]+((g>0)?tut[0][1][r][g-1]:0) +((y>0)?tut[0][2][r][y-1]:0)-sira);
	}
	if(son!=1&&g<green.size()){
		cev=min(cev,hesap(r,g+1,y,1,sira+1)+green[g]+((r>0)?tut[1][0][g][r-1]:0 )+((y>0)?tut[1][2][g][y-1]:0)-sira);
	}
	if(son!=2&&y<yellow.size()){
		cev=min(cev,hesap(r,g,y+1,2,sira+1)+yellow[y]+((r>0)?tut[2][0][y][r-1]:0) +((g>0)?tut[2][1][y][g-1]:0)-sira);
	}
	//cout<<cev<<" "<<r<<" "<<g<<" "<<y<<" "<<son<<" "<<sira<<endl;
	return dp[r][g][y][son]=cev;
}

int arr[N];
int main(){
	lalala;
	memset(dp,-1,sizeof(dp));
	cin>>n;
	string str;cin>>str;
	for(int i=0;i<n;i++){
		if(str[i]=='G')green.pb(i);
		if(str[i]=='R')red.pb(i);
		if(str[i]=='Y')yellow.pb(i);
	}
	for(int i=0;i<red.size();i++){
		int kac=0;
		for(int j=0;j<green.size();j++){
			if(red[i]<green[j])	kac++;
			
			tut[0][1][i][j]=kac;
		}
	}
	for(int i=0;i<red.size();i++){
		int kac=0;
		for(int j=0;j<yellow.size();j++){
			if(red[i]<yellow[j]) kac++;

			tut[0][2][i][j]=kac;
		}
	}
	for(int i=0;i<green.size();i++){
		int kac=0;
		for(int j=0;j<red.size();j++){
			if(green[i]<red[j]) kac++;
			
			tut[1][0][i][j]=kac;
		}
	}
	for(int i=0;i<green.size();i++){
		int kac=0;
		for(int j=0;j<yellow.size();j++){
			if(green[i]<yellow[j]) kac++;
			
			tut[1][2][i][j]=kac;
		}
	}
	for(int i=0;i<yellow.size();i++){
		int kac=0;
		for(int j=0;j<red.size();j++){
			if(yellow[i]<red[j]) kac++;
			tut[2][0][i][j]=kac;
			
		}
	}
	for(int i=0;i<yellow.size();i++){
		int kac=0;
		for(int j=0;j<green.size();j++){
			if(yellow[i]<green[j]) kac++;
			tut[2][1][i][j]=kac;
			
		}
	}
	int a=hesap(0,0,0,0,0);
	if(a>=1000000000)a=-1;
	cout<<a<<endl;

}

Compilation message

joi2019_ho_t3.cpp: In function 'int hesap(int, int, int, int, int)':
joi2019_ho_t3.cpp:16:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  if((son!=0||r+g+y==0)&&r<red.size()){
      |                         ~^~~~~~~~~~~
joi2019_ho_t3.cpp:19:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  if(son!=1&&g<green.size()){
      |             ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  if(son!=2&&y<yellow.size()){
      |             ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0;i<red.size();i++){
      |              ~^~~~~~~~~~~
joi2019_ho_t3.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(int j=0;j<green.size();j++){
      |               ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=0;i<red.size();i++){
      |              ~^~~~~~~~~~~
joi2019_ho_t3.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int j=0;j<yellow.size();j++){
      |               ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |  for(int i=0;i<green.size();i++){
      |              ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |   for(int j=0;j<red.size();j++){
      |               ~^~~~~~~~~~~
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<green.size();i++){
      |              ~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int j=0;j<yellow.size();j++){
      |               ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:72:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for(int i=0;i<yellow.size();i++){
      |              ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:74:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for(int j=0;j<red.size();j++){
      |               ~^~~~~~~~~~~
joi2019_ho_t3.cpp:80:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0;i<yellow.size();i++){
      |              ~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:82:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for(int j=0;j<green.size();j++){
      |               ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 780248 KB Output is correct
2 Correct 234 ms 780232 KB Output is correct
3 Correct 263 ms 780312 KB Output is correct
4 Correct 233 ms 780252 KB Output is correct
5 Correct 235 ms 780312 KB Output is correct
6 Correct 241 ms 780400 KB Output is correct
7 Correct 235 ms 780332 KB Output is correct
8 Correct 236 ms 780372 KB Output is correct
9 Correct 267 ms 780284 KB Output is correct
10 Correct 237 ms 780236 KB Output is correct
11 Correct 233 ms 780364 KB Output is correct
12 Correct 245 ms 780368 KB Output is correct
13 Correct 232 ms 780360 KB Output is correct
14 Correct 232 ms 780272 KB Output is correct
15 Correct 247 ms 780356 KB Output is correct
16 Correct 234 ms 780256 KB Output is correct
17 Correct 237 ms 780264 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 780248 KB Output is correct
2 Correct 234 ms 780232 KB Output is correct
3 Correct 263 ms 780312 KB Output is correct
4 Correct 233 ms 780252 KB Output is correct
5 Correct 235 ms 780312 KB Output is correct
6 Correct 241 ms 780400 KB Output is correct
7 Correct 235 ms 780332 KB Output is correct
8 Correct 236 ms 780372 KB Output is correct
9 Correct 267 ms 780284 KB Output is correct
10 Correct 237 ms 780236 KB Output is correct
11 Correct 233 ms 780364 KB Output is correct
12 Correct 245 ms 780368 KB Output is correct
13 Correct 232 ms 780360 KB Output is correct
14 Correct 232 ms 780272 KB Output is correct
15 Correct 247 ms 780356 KB Output is correct
16 Correct 234 ms 780256 KB Output is correct
17 Correct 237 ms 780264 KB Output is correct
18 Correct 250 ms 780664 KB Output is correct
19 Correct 233 ms 780444 KB Output is correct
20 Correct 233 ms 780512 KB Output is correct
21 Correct 244 ms 780468 KB Output is correct
22 Correct 234 ms 780408 KB Output is correct
23 Correct 237 ms 780492 KB Output is correct
24 Correct 241 ms 780476 KB Output is correct
25 Correct 233 ms 780484 KB Output is correct
26 Correct 232 ms 780412 KB Output is correct
27 Correct 242 ms 780436 KB Output is correct
28 Correct 234 ms 780408 KB Output is correct
29 Correct 236 ms 780408 KB Output is correct
30 Correct 242 ms 780532 KB Output is correct
31 Correct 234 ms 780424 KB Output is correct
32 Correct 234 ms 780528 KB Output is correct
33 Correct 249 ms 780504 KB Output is correct
34 Correct 249 ms 780468 KB Output is correct
35 Correct 256 ms 780496 KB Output is correct
36 Correct 234 ms 780416 KB Output is correct
37 Correct 237 ms 780424 KB Output is correct
38 Correct 241 ms 780556 KB Output is correct
39 Correct 233 ms 780492 KB Output is correct
40 Correct 235 ms 780304 KB Output is correct
41 Correct 255 ms 780432 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 780204 KB Output is correct
2 Correct 233 ms 780924 KB Output is correct
3 Correct 248 ms 780920 KB Output is correct
4 Correct 235 ms 780956 KB Output is correct
5 Correct 235 ms 780996 KB Output is correct
6 Correct 248 ms 780876 KB Output is correct
7 Correct 234 ms 780940 KB Output is correct
8 Correct 236 ms 780880 KB Output is correct
9 Correct 242 ms 780968 KB Output is correct
10 Correct 242 ms 780940 KB Output is correct
11 Correct 236 ms 780928 KB Output is correct
12 Correct 245 ms 780624 KB Output is correct
13 Correct 237 ms 780744 KB Output is correct
14 Correct 236 ms 781000 KB Output is correct
15 Correct 246 ms 781080 KB Output is correct
16 Correct 236 ms 780948 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 780248 KB Output is correct
2 Correct 234 ms 780232 KB Output is correct
3 Correct 263 ms 780312 KB Output is correct
4 Correct 233 ms 780252 KB Output is correct
5 Correct 235 ms 780312 KB Output is correct
6 Correct 241 ms 780400 KB Output is correct
7 Correct 235 ms 780332 KB Output is correct
8 Correct 236 ms 780372 KB Output is correct
9 Correct 267 ms 780284 KB Output is correct
10 Correct 237 ms 780236 KB Output is correct
11 Correct 233 ms 780364 KB Output is correct
12 Correct 245 ms 780368 KB Output is correct
13 Correct 232 ms 780360 KB Output is correct
14 Correct 232 ms 780272 KB Output is correct
15 Correct 247 ms 780356 KB Output is correct
16 Correct 234 ms 780256 KB Output is correct
17 Correct 237 ms 780264 KB Output is correct
18 Correct 250 ms 780664 KB Output is correct
19 Correct 233 ms 780444 KB Output is correct
20 Correct 233 ms 780512 KB Output is correct
21 Correct 244 ms 780468 KB Output is correct
22 Correct 234 ms 780408 KB Output is correct
23 Correct 237 ms 780492 KB Output is correct
24 Correct 241 ms 780476 KB Output is correct
25 Correct 233 ms 780484 KB Output is correct
26 Correct 232 ms 780412 KB Output is correct
27 Correct 242 ms 780436 KB Output is correct
28 Correct 234 ms 780408 KB Output is correct
29 Correct 236 ms 780408 KB Output is correct
30 Correct 242 ms 780532 KB Output is correct
31 Correct 234 ms 780424 KB Output is correct
32 Correct 234 ms 780528 KB Output is correct
33 Correct 249 ms 780504 KB Output is correct
34 Correct 249 ms 780468 KB Output is correct
35 Correct 256 ms 780496 KB Output is correct
36 Correct 234 ms 780416 KB Output is correct
37 Correct 237 ms 780424 KB Output is correct
38 Correct 241 ms 780556 KB Output is correct
39 Correct 233 ms 780492 KB Output is correct
40 Correct 235 ms 780304 KB Output is correct
41 Correct 255 ms 780432 KB Output is correct
42 Correct 236 ms 780204 KB Output is correct
43 Correct 233 ms 780924 KB Output is correct
44 Correct 248 ms 780920 KB Output is correct
45 Correct 235 ms 780956 KB Output is correct
46 Correct 235 ms 780996 KB Output is correct
47 Correct 248 ms 780876 KB Output is correct
48 Correct 234 ms 780940 KB Output is correct
49 Correct 236 ms 780880 KB Output is correct
50 Correct 242 ms 780968 KB Output is correct
51 Correct 242 ms 780940 KB Output is correct
52 Correct 236 ms 780928 KB Output is correct
53 Correct 245 ms 780624 KB Output is correct
54 Correct 237 ms 780744 KB Output is correct
55 Correct 236 ms 781000 KB Output is correct
56 Correct 246 ms 781080 KB Output is correct
57 Correct 236 ms 780948 KB Output is correct
58 Correct 311 ms 781520 KB Output is correct
59 Correct 314 ms 781516 KB Output is correct
60 Correct 314 ms 781600 KB Output is correct
61 Correct 336 ms 781632 KB Output is correct
62 Correct 327 ms 781600 KB Output is correct
63 Correct 245 ms 781592 KB Output is correct
64 Correct 246 ms 781532 KB Output is correct
65 Correct 300 ms 781560 KB Output is correct
66 Correct 332 ms 781648 KB Output is correct
67 Correct 319 ms 781516 KB Output is correct
68 Correct 324 ms 781628 KB Output is correct
69 Correct 324 ms 781516 KB Output is correct
70 Correct 317 ms 781604 KB Output is correct
71 Correct 332 ms 781704 KB Output is correct
72 Correct 238 ms 781528 KB Output is correct
73 Correct 231 ms 781496 KB Output is correct