oj.uz

답안 #919863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919863 2024-02-01T18:24:52 Z vjudge1 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
100 / 100
 320 ms 783444 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:30: 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:18: 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:18: 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:19: 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:20: 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:19: 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:20: 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:19: 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:20: 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:19: 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:20: 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:19: 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:20: 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:19: 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:20: 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

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 782264 KB Output is correct
2 Correct 253 ms 782656 KB Output is correct
3 Correct 245 ms 782416 KB Output is correct
4 Correct 236 ms 782416 KB Output is correct
5 Correct 235 ms 782384 KB Output is correct
6 Correct 226 ms 782416 KB Output is correct
7 Correct 228 ms 782448 KB Output is correct
8 Correct 224 ms 782428 KB Output is correct
9 Correct 226 ms 782452 KB Output is correct
10 Correct 229 ms 782372 KB Output is correct
11 Correct 218 ms 782352 KB Output is correct
12 Correct 224 ms 782596 KB Output is correct
13 Correct 220 ms 782460 KB Output is correct
14 Correct 222 ms 782284 KB Output is correct
15 Correct 222 ms 782340 KB Output is correct
16 Correct 220 ms 782440 KB Output is correct
17 Correct 220 ms 782676 KB Output is correct

Subtask #2
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 782264 KB Output is correct
2 Correct 253 ms 782656 KB Output is correct
3 Correct 245 ms 782416 KB Output is correct
4 Correct 236 ms 782416 KB Output is correct
5 Correct 235 ms 782384 KB Output is correct
6 Correct 226 ms 782416 KB Output is correct
7 Correct 228 ms 782448 KB Output is correct
8 Correct 224 ms 782428 KB Output is correct
9 Correct 226 ms 782452 KB Output is correct
10 Correct 229 ms 782372 KB Output is correct
11 Correct 218 ms 782352 KB Output is correct
12 Correct 224 ms 782596 KB Output is correct
13 Correct 220 ms 782460 KB Output is correct
14 Correct 222 ms 782284 KB Output is correct
15 Correct 222 ms 782340 KB Output is correct
16 Correct 220 ms 782440 KB Output is correct
17 Correct 220 ms 782676 KB Output is correct
18 Correct 217 ms 782488 KB Output is correct
19 Correct 217 ms 782420 KB Output is correct
20 Correct 216 ms 782288 KB Output is correct
21 Correct 218 ms 782288 KB Output is correct
22 Correct 220 ms 782528 KB Output is correct
23 Correct 217 ms 782484 KB Output is correct
24 Correct 219 ms 782364 KB Output is correct
25 Correct 212 ms 782420 KB Output is correct
26 Correct 217 ms 782420 KB Output is correct
27 Correct 216 ms 782504 KB Output is correct
28 Correct 223 ms 782428 KB Output is correct
29 Correct 218 ms 782332 KB Output is correct
30 Correct 215 ms 782328 KB Output is correct
31 Correct 218 ms 782568 KB Output is correct
32 Correct 218 ms 782416 KB Output is correct
33 Correct 218 ms 782316 KB Output is correct
34 Correct 216 ms 782448 KB Output is correct
35 Correct 217 ms 782672 KB Output is correct
36 Correct 220 ms 782416 KB Output is correct
37 Correct 221 ms 782412 KB Output is correct
38 Correct 223 ms 782572 KB Output is correct
39 Correct 215 ms 782416 KB Output is correct
40 Correct 213 ms 782416 KB Output is correct
41 Correct 217 ms 782328 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 217 ms 782340 KB Output is correct
2 Correct 215 ms 782516 KB Output is correct
3 Correct 215 ms 782676 KB Output is correct
4 Correct 227 ms 782780 KB Output is correct
5 Correct 213 ms 782572 KB Output is correct
6 Correct 221 ms 782944 KB Output is correct
7 Correct 216 ms 782672 KB Output is correct
8 Correct 220 ms 782640 KB Output is correct
9 Correct 219 ms 782672 KB Output is correct
10 Correct 216 ms 782672 KB Output is correct
11 Correct 216 ms 782676 KB Output is correct
12 Correct 226 ms 782444 KB Output is correct
13 Correct 219 ms 782396 KB Output is correct
14 Correct 217 ms 782416 KB Output is correct
15 Correct 220 ms 782492 KB Output is correct
16 Correct 219 ms 782600 KB Output is correct

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 320 ms 782264 KB Output is correct
2 Correct 253 ms 782656 KB Output is correct
3 Correct 245 ms 782416 KB Output is correct
4 Correct 236 ms 782416 KB Output is correct
5 Correct 235 ms 782384 KB Output is correct
6 Correct 226 ms 782416 KB Output is correct
7 Correct 228 ms 782448 KB Output is correct
8 Correct 224 ms 782428 KB Output is correct
9 Correct 226 ms 782452 KB Output is correct
10 Correct 229 ms 782372 KB Output is correct
11 Correct 218 ms 782352 KB Output is correct
12 Correct 224 ms 782596 KB Output is correct
13 Correct 220 ms 782460 KB Output is correct
14 Correct 222 ms 782284 KB Output is correct
15 Correct 222 ms 782340 KB Output is correct
16 Correct 220 ms 782440 KB Output is correct
17 Correct 220 ms 782676 KB Output is correct
18 Correct 217 ms 782488 KB Output is correct
19 Correct 217 ms 782420 KB Output is correct
20 Correct 216 ms 782288 KB Output is correct
21 Correct 218 ms 782288 KB Output is correct
22 Correct 220 ms 782528 KB Output is correct
23 Correct 217 ms 782484 KB Output is correct
24 Correct 219 ms 782364 KB Output is correct
25 Correct 212 ms 782420 KB Output is correct
26 Correct 217 ms 782420 KB Output is correct
27 Correct 216 ms 782504 KB Output is correct
28 Correct 223 ms 782428 KB Output is correct
29 Correct 218 ms 782332 KB Output is correct
30 Correct 215 ms 782328 KB Output is correct
31 Correct 218 ms 782568 KB Output is correct
32 Correct 218 ms 782416 KB Output is correct
33 Correct 218 ms 782316 KB Output is correct
34 Correct 216 ms 782448 KB Output is correct
35 Correct 217 ms 782672 KB Output is correct
36 Correct 220 ms 782416 KB Output is correct
37 Correct 221 ms 782412 KB Output is correct
38 Correct 223 ms 782572 KB Output is correct
39 Correct 215 ms 782416 KB Output is correct
40 Correct 213 ms 782416 KB Output is correct
41 Correct 217 ms 782328 KB Output is correct
42 Correct 217 ms 782340 KB Output is correct
43 Correct 215 ms 782516 KB Output is correct
44 Correct 215 ms 782676 KB Output is correct
45 Correct 227 ms 782780 KB Output is correct
46 Correct 213 ms 782572 KB Output is correct
47 Correct 221 ms 782944 KB Output is correct
48 Correct 216 ms 782672 KB Output is correct
49 Correct 220 ms 782640 KB Output is correct
50 Correct 219 ms 782672 KB Output is correct
51 Correct 216 ms 782672 KB Output is correct
52 Correct 216 ms 782676 KB Output is correct
53 Correct 226 ms 782444 KB Output is correct
54 Correct 219 ms 782396 KB Output is correct
55 Correct 217 ms 782416 KB Output is correct
56 Correct 220 ms 782492 KB Output is correct
57 Correct 219 ms 782600 KB Output is correct
58 Correct 277 ms 783100 KB Output is correct
59 Correct 279 ms 783220 KB Output is correct
60 Correct 279 ms 783184 KB Output is correct
61 Correct 285 ms 783260 KB Output is correct
62 Correct 217 ms 782928 KB Output is correct
63 Correct 215 ms 782928 KB Output is correct
64 Correct 231 ms 782928 KB Output is correct
65 Correct 253 ms 783080 KB Output is correct
66 Correct 280 ms 783184 KB Output is correct
67 Correct 280 ms 783184 KB Output is correct
68 Correct 287 ms 783052 KB Output is correct
69 Correct 299 ms 783188 KB Output is correct
70 Correct 286 ms 783160 KB Output is correct
71 Correct 296 ms 783440 KB Output is correct
72 Correct 216 ms 782672 KB Output is correct
73 Correct 214 ms 783444 KB Output is correct