Submission #478560

#	Time	Username	Problem	Language	Result	Execution time	Memory
478560		Mackerel_Pike	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	101 ms	4176 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int maxn = 405;

int n;
int a[3][maxn], b[maxn][3], cnt[3];
int f[2][maxn][maxn][3];
char s[maxn];

inline int calc(int i, int j, int k, int l){
  return max(j - b[i][0], 0) + max(k - b[i][1], 0) + max(l - b[i][2], 0);
}

int main(){
  //freopen("b.in", "r", stdin);
  //freopen("b.out", "w", stdout);
  
  scanf("%d", &n);
  scanf("%s", s);


  for(int i = 0; i < n; ++i){
    for(int j = 0; j < 3; ++j)
      b[i][j] = cnt[j];
    s[i] = (s[i] == 'R' ? 2 : (s[i] == 'G'));
    a[s[i]][cnt[s[i]]++] = i;
  }

  int p = 0, q = 1;
  memset(f[p], 0x3f, sizeof(f[p]));
  if(cnt[0])
    f[p][1][0][0] = 0;
  if(cnt[1])
    f[p][0][1][1] = 0;
  if(cnt[2])
    f[p][0][0][2] = 0;
  for(int i = 1; i <= n - 1; ++i){
    memset(f[q], 0x3f, sizeof(f[q]));
    for(int j = 0; j <= i; ++j)
      for(int k = 0; k <= i - j; ++k){
	int l = i - j - k;
	for(int s = 0; s < 3; ++s)
	  if(f[p][j][k][s] != 0x3f3f3f3f){
	    if(s != 0 && j + 1 <= cnt[0])
	      f[q][j + 1][k][0] = min(f[q][j + 1][k][0], f[p][j][k][s] + calc(a[0][j], j, k, l));
	    if(s != 1 && k + 1 <= cnt[1])
	      f[q][j][k + 1][1] = min(f[q][j][k + 1][1], f[p][j][k][s] + calc(a[1][k], j, k, l));
	    if(s != 2 && l + 1 <= cnt[2])
	      f[q][j][k][2]     = min(f[q][j][k][2]    , f[p][j][k][s] + calc(a[2][l], j, k, l));
	  }
      }
    swap(p, q);
  }

  int ans = 0x3f3f3f3f;
  for(int i = 0; i < 3; ++i)
    ans = min(ans, f[p][cnt[0]][cnt[1]][i]);

  printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
  return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:28:10: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |     a[s[i]][cnt[s[i]]++] = i;
      |       ~~~^
joi2019_ho_t3.cpp:28:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   28 |     a[s[i]][cnt[s[i]]++] = i;
      |                 ~~~^
joi2019_ho_t3.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
joi2019_ho_t3.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |   scanf("%s", s);
      |   ~~~~~^~~~~~~~~

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