Submission #127619

#	Time	Username	Problem	Language	Result	Execution time	Memory
127619		IOrtroiii	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	81 ms	31096 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int inf = 1e9;

char s[405];
int cnt[3];
int pref[405][3];
int where[405][3];
vector<vector<vector<int>>> f[3];

int conv(char c) {
   if (c == 'R') return 0;
   else if (c == 'G') return 1;
   return 2;
}

int main() {
   ios_base::sync_with_stdio(false);
   int n;
   scanf("%d %s", &n, s + 1);
   for (int i = 1; i <= n; ++i) {
      int t = conv(s[i]);
      where[++cnt[t]][t] = i;
      for (int j = 0; j < 3; ++j) {
         pref[i][j] = cnt[j];
      }
   }
   for (int i = 0; i < 3; ++i) {
      f[i].resize(cnt[0] + 1);
      for (auto& f2 : f[i]) {
         f2.resize(cnt[1] + 1);
         for (auto& f3 : f2) {
            f3.assign(cnt[2] + 1, inf);
         }
      }
   }
   f[0][0][0][0] = f[1][0][0][0] = f[2][0][0][0] = 0;
   for (int x = 0; x <= cnt[0]; ++x) {
      for (int y = 0; y <= cnt[1]; ++y) {
         for (int z = 0; z <= cnt[2]; ++z) {
            if (x < cnt[0]) {
               int cost = min(f[1][x][y][z], f[2][x][y][z]);
               int wh = where[x + 1][0];
               cost += max(0, y - pref[wh][1]) + max(0, z - pref[wh][2]);
               f[0][x + 1][y][z] = min(f[0][x + 1][y][z], cost);
            }
            if (y < cnt[1]) {
               int cost = min(f[0][x][y][z], f[2][x][y][z]);
               int wh = where[y + 1][1];
               cost += max(0, x - pref[wh][0]) + max(0, z - pref[wh][2]);
               f[1][x][y + 1][z] = min(f[1][x][y + 1][z], cost);
            }
            if (z < cnt[2]) {
               int cost = min(f[0][x][y][z], f[1][x][y][z]);
               int wh = where[z + 1][2];
               cost += max(0, x - pref[wh][0]) + max(0, y - pref[wh][1]);
               f[2][x][y][z + 1] = min(f[2][x][y][z + 1], cost);
            }
         }
      }
   }
   int ans = min({f[0][cnt[0]][cnt[1]][cnt[2]], f[1][cnt[0]][cnt[1]][cnt[2]], f[2][cnt[0]][cnt[1]][cnt[2]]});
   if (ans == inf) ans = -1;
   printf("%d\n", ans);
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:22:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %s", &n, s + 1);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

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