Submission #128448

#	Time	Username	Problem	Language	Result	Execution time	Memory
128448		dragonslayerit	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	136 ms	163072 KiB

joi2019_ho_t3

#include <cstdio>
#include <algorithm>
#include <vector>

const int INF=1e9+7;

int dp[401][401][401][3];

std::vector<int> where[3];

char rgy[]="RGY";

int N;
char str[405];

int main(){
  scanf("%d %s",&N,str);
  for(int i=0;i<N;i++){
    where[std::find(rgy,rgy+3,str[i])-rgy].push_back(i+1);
  }
  for(int a=0;a<=where[0].size();a++){
    for(int b=0;b<=where[1].size();b++){
      for(int c=0;c<=where[2].size();c++){
	std::fill(dp[a][b][c],dp[a][b][c]+3,(a+b+c==0)?0:INF);
	if(a) dp[a][b][c][0]=std::abs(a+b+c-where[0][a-1])+std::min(dp[a-1][b][c][1],dp[a-1][b][c][2]);
	if(b) dp[a][b][c][1]=std::abs(a+b+c-where[1][b-1])+std::min(dp[a][b-1][c][2],dp[a][b-1][c][0]);
	if(c) dp[a][b][c][2]=std::abs(a+b+c-where[2][c-1])+std::min(dp[a][b][c-1][0],dp[a][b][c-1][1]);
	//auto x=dp[a][b][c];
	//printf("dp[%d][%d][%d]: %d %d %d\n",a,b,c,x[0],x[1],x[2]);
      }
    }
  }
  auto x=dp[where[0].size()][where[1].size()][where[2].size()];
  int ans=*std::min_element(x,x+3);
  printf("%d\n",ans<INF?ans/2:-1);
  return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:21:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int a=0;a<=where[0].size();a++){
               ~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b=0;b<=where[1].size();b++){
                 ~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int c=0;c<=where[2].size();c++){
                   ~^~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %s",&N,str);
   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25