Submission #474177

#	Time	Username	Problem	Language	Result	Execution time	Memory
474177		ntabc05101	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	172 ms	28744 KiB

joi2019_ho_t3

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

#define taskname ""

const int inf = 1e9 + 9;
const string bs = "RGY";

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }

  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;
  string s; cin >> s;
  vector<int> pos[3];
  int prf[3][n + 1];
  for (int t = 0; t < 3; t++) {
    prf[t][0] = 0;
    pos[t].push_back(0);
    for (int i = 0; i < n; i++) {
      prf[t][i + 1] = prf[t][i];
      if (s[i] == bs[t]) {
        pos[t].push_back(i + 1);
        prf[t][i + 1]++;
      }
    }
  }

  int dp[3][prf[0][n] + 1][prf[1][n] + 1][prf[2][n] + 1];
  for (int t = 0; t < 3; t++) {
    for (int i = 0; i <= prf[0][n]; i++) {
      for (int j = 0; j <= prf[1][n]; j++) {
        for (int k = 0; k <= prf[2][n]; k++) {
          dp[t][i][j][k] = inf;
        }
      }
    }
    dp[t][0][0][0] = 0;
  }

  //cout << prf[0][n] << " " << prf[1][n] << " " << prf[2][n] << "\n";
  /*for (int t = 0; t < 3; t++) {
    cout << dp[t][prf[0][n]][prf[1][n]][prf[2][n]] << "\n";
  }*/

  int z[3];
  for (z[0] = 0; z[0] <= prf[0][n]; z[0]++) {
    for (z[1] = 0; z[1] <= prf[1][n]; z[1]++) {
      for (z[2] = 0; z[2] <= prf[2][n]; z[2]++) {
        for (int prv = 0; prv < 3; prv++) {
          for (int cur = 0; cur < 3; cur++) {
            if (cur == prv || z[cur] == prf[cur][n]) {
              continue;
            }
            int res = dp[prv][z[0]][z[1]][z[2]];
            int dff = ((cur + 1) ^ (prv + 1)) - 1;
            int p1 = pos[cur][z[cur] + 1], p2 = pos[prv][z[prv]], p3 = pos[dff][z[dff]];
            res += max(0, prf[prv][p1] - prf[prv][p2]) + max(0, prf[dff][p1] - prf[dff][p3]);
            p1 = z[0] + (cur == 0); p2 = z[1] + (cur == 1); p3 = z[2] + (cur == 2);
            dp[cur][p1][p2][p3] = min(dp[cur][p1][p2][p3], res);
          }
        }
      }
    }
  }

  int res = inf;
  for (int t = 0; t < 3; t++) {
    //cout << res << "\n";
    res = min(res, dp[t][prf[0][n]][prf[1][n]][prf[2][n]]);
  }

  cout << (res == inf ? -1: res) << "\n";

  return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:11:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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