oj.uz

Submission #788656

# Submission time Handle Problem Language Result Execution time Memory
788656 2023-07-20T12:52:05 Z tvladm2009 Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 51 ms 162952 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = (int) 4e2 + 7;
const int INF = (int) 1e9;
int n;
int a[N];
int cnt[3][N][3];
int dp[N][N][N][3];
string s;

int decode(char ch) {
  if (ch == 'R') {
    return 0;
  } else if (ch == 'G') {
    return 1;
  } else if (ch == 'Y') {
    return 2;
  }
  assert(0);
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  // freopen("input", "r", stdin);

  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    a[i] = decode(s[i - 1]);    
  }
  int cnta = 0, cntb = 0, cntc = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0) {
      cnta++;
      cnt[0][cntc][1] = cntb;
      cnt[0][cntc][2] = cntc;
    } else if (a[i] == 1) {
      cntb++;
      cnt[1][cntb][0] = cnta;
      cnt[1][cntb][2] = cntc;
    } else {
      cntc++;
      cnt[2][cntc][0] = cnta;
      cnt[2][cntc][1] = cntb;
    }
  }
  for (int a = 0; a <= cnta; a++) {
    for (int b = 0; b <= cntb; b++) {
      for (int c = 0; c <= cntc; c++) {
        dp[a][b][c][0] = INF;
        dp[a][b][c][1] = INF;
        dp[a][b][c][2] = INF;
      }
    }
  }
  dp[0][0][0][0] = 0;
  dp[0][0][0][1] = 0;
  dp[0][0][0][2] = 0;
  for (int a = 0; a <= cnta; a++) {
    for (int b = 0; b <= cntb; b++) {
      for (int c = 0; c <= cntc; c++) {
        if (a < cnta) {
          dp[a + 1][b][c][0] = min(dp[a + 1][b][c][0], min(dp[a][b][c][1], dp[a][b][c][2]) + abs(b - cnt[0][a + 1][1]) + abs(c - cnt[0][a + 1][2]));
        }
        if (b < cntb) {
          dp[a][b + 1][c][1] = min(dp[a][b + 1][c][1], min(dp[a][b][c][0], dp[a][b][c][2]) + abs(a - cnt[1][b + 1][0]) + abs(c - cnt[1][b + 1][2]));
        }
        if (c < cntc) {
          dp[a][b][c + 1][2] = min(dp[a][b][c + 1][2], min(dp[a][b][c][0], dp[a][b][c][1]) + abs(a - cnt[2][c + 1][0]) + abs(b - cnt[2][c + 1][1]));
        }
      }
    }
  }
  int sol = INF;
  sol = min(sol, dp[cnta][cntb][cntc][0]);
  sol = min(sol, dp[cnta][cntb][cntc][1]);
  sol = min(sol, dp[cnta][cntb][cntc][2]);
  if (sol == INF) {
    cout << "-1\n";
    return 0;
  }
  cout << sol / 2;
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 51 ms 162952 KB Output is correct
3 Correct 51 ms 162128 KB Output is correct
4 Incorrect 51 ms 162948 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -