Submission #919863

#	Time	Username	Problem	Language	Result	Execution time	Memory
919863		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	320 ms	783444 KiB

joi2019_ho_t3

    #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 (stderr)

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 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25