Submission #864316

#	Time	Username	Problem	Language	Result	Execution time	Memory
864316		rxlfd314	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	14 ms	18524 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = a > (b) ? a : (b))
#define chmin(a, b) (a = a < (b) ? a : (b))

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  int N;
  cin >> N;
  int R = 0, G = 0, Y = 0;
  vt<int> inds[3];
  FOR(i, 1, N) {
    char c;
    cin >> c;
    int a = (c == 'G') + (c == 'Y') * 2;
    R += c == 'R';
    G += c == 'G';
    Y += c == 'Y';
    inds[a].push_back(i);
  }
  constexpr int INF = 0x3f3f3f3f;
  vt<vt<vt<vt<int>>>> dp(3, vt<vt<vt<int>>>(R+1, vt<vt<int>>(G+1, vt<int>(Y+1, INF))));
  dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;
  FOR(r, 0, R)
    FOR(g, 0, G)
      FOR(y, 0, Y) {
        if (!r && !g && !y)
          continue;
        int i = r + g + y;
        if (r)
          dp[0][r][g][y] = min(dp[1][r-1][g][y], dp[2][r-1][g][y]) + abs(inds[0][r-1] - i);
        if (g)
          dp[1][r][g][y] = min(dp[0][r][g-1][y], dp[2][r][g-1][y]) + abs(inds[1][g-1] - i);
        if (y)
          dp[2][r][g][y] = min(dp[0][r][g][y-1], dp[1][r][g][y-1]) + abs(inds[2][y-1] - i);
      }
  int ans = min({dp[0][R][G][Y], dp[1][R][G][Y], dp[2][R][G][Y]});
  assert(!(ans & 1));
  cout << (ans < INF ? ans / 2 : -1) << '\n';
}

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