oj.uz

Submission #864313

# Submission time Handle Problem Language Result Execution time Memory
864313 2023-10-22T11:30:56 Z rxlfd314 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 10 ms 9312 KB 
#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, 0, N-1) {
    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 - 1;
        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]});
  cout << (ans < INF ? ans / 2 : -1) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 8 ms 9308 KB Output is correct
3 Correct 10 ms 9184 KB Output is correct
4 Correct 8 ms 9308 KB Output is correct
5 Correct 8 ms 9216 KB Output is correct
6 Correct 8 ms 9308 KB Output is correct
7 Correct 8 ms 9048 KB Output is correct
8 Correct 8 ms 9312 KB Output is correct
9 Correct 8 ms 9052 KB Output is correct
10 Correct 8 ms 9308 KB Output is correct
11 Correct 8 ms 9308 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 4 ms 4444 KB Output is correct
14 Correct 5 ms 6488 KB Output is correct
15 Correct 8 ms 9164 KB Output is correct
16 Correct 8 ms 9304 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 456 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Incorrect 0 ms 348 KB Output isn't correct
12 Halted 0 ms 0 KB -