Submission #1223177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223177		fermat	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	72 ms	163656 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 405;

int dp[N][N][N][3], n, in[3][N], cnt[3], cn[3][2][N][N];

string s;

inline int min(int a, int b) {
 return a < b ? a : b;
}

main(){
 cin >> n >> s;
 s = ' ' + s;
 
 for (int i = 1; i <= n; i++) {
  
  if (s[i] == 'R') {
   cnt[0]++;
   in[0][cnt[0]] = i;
  }
  else if (s[i] == 'G') {
   cnt[1]++;
   in[1][cnt[1]] = i;
  }
  else {
   cnt[2]++;
   in[2][cnt[2]] = i;
  }
 }
 for (int i = 1; i <= cnt[0]; i++) {
  for (int j = 1; j <= cnt[1]; j++) {
   if ( in[1][j] > in[0][i] )
    cn[0][0][i][j] = cn[0][0][i][j - 1] + 1; 
  }
  for (int j = 1; j <= cnt[2]; j++) {
   if ( in[2][j] > in[0][i] )
    cn[0][1][i][j] = cn[0][1][i][j - 1] + 1;
  }
 }
 for (int i = 1; i <= cnt[1]; i++) {
  for (int j = 1; j <= cnt[0]; j++) {
   if ( in[0][j] > in[1][i] )
    cn[1][0][i][j] = cn[1][0][i][j - 1] + 1; 
  }
  for (int j = 1; j <= cnt[2]; j++) {
   if ( in[2][j] > in[1][i] )
    cn[1][1][i][j] = cn[1][1][i][j - 1] + 1;
  }
 }
 for (int i = 1; i <= cnt[2]; i++) {
  for (int j = 1; j <= cnt[1]; j++) {
   if ( in[1][j] > in[2][i] )
    cn[2][0][i][j] = cn[2][0][i][j - 1] + 1; 
  }
  for (int j = 1; j <= cnt[0]; j++) {
   if ( in[0][j] > in[2][i] )
    cn[2][1][i][j] = cn[2][1][i][j - 1] + 1;
  }
 }
 for (int i = 0; i <= cnt[0]; i++)
  for (int j = 0; j <= cnt[1]; j++)
   for (int k = 0; k <= cnt[2]; k++)
    for (int last = 0; last < 3; last++)
     dp[i][j][k][last] = 1e9 + 7;
     
 dp[0][0][0][0] = 0;
 dp[0][0][0][1] = 0;
 dp[0][0][0][2] = 0;
 
 for (int i = 0; i <= cnt[0]; i++) {
  for (int j = 0; j <= cnt[1]; j++) {
   for (int k = 0; k <= cnt[2]; k++) {
    for (int last = 0; last < 3; last++) {
     
     if (i + 1 <= cnt[0] && last != 0)
      dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[0][i + 1] + cn[0][0][i + 1][j] + cn[0][1][i + 1][k]) ) );
     
     if (j + 1 <= cnt[1] && last != 1)
      dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[1][j + 1] + cn[1][0][j + 1][i] + cn[1][1][j + 1][k]) ) );
     
     if (k + 1 <= cnt[2] && last != 2){
      dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], dp[i][j][k][last] + abs( (i + j + k + 1) - (in[2][k + 1] + cn[2][0][k + 1][j] + cn[2][1][k + 1][i]) ) );
     }
    }
   }
  }
 }
 if ( min( dp[cnt[0]][cnt[1]][cnt[2]][0], min( dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2] ) ) > 1e9 )
  cout << -1 << endl;
 else
  cout << min( dp[cnt[0]][cnt[1]][cnt[2]][0], min( dp[cnt[0]][cnt[1]][cnt[2]][1], dp[cnt[0]][cnt[1]][cnt[2]][2] ) ) << endl;
}

Compilation message (stderr)

joi2019_ho_t3.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main(){
      | ^~~~

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