Submission #818788

#	Time	Username	Problem	Language	Result	Execution time	Memory
818788		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	557 ms	1040344 KiB

joi2019_ho_t3

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

const int MX = 405;

int N;
string s;
int dp[MX][MX][MX][4];
vector<int> R, G, Y;

int f(int r, int g, int y, int l) {
      if(r + g + y == N) return 0;
      if(dp[r][g][y][l] != -1) return dp[r][g][y][l];

      int res = 1e9;
      if(r < R.size() && l != 0) {
            auto gg = upper_bound(G.begin(), G.end(), R[r]) - G.begin();
            auto yy = upper_bound(Y.begin(), Y.end(), R[r]) - Y.begin();

            int cost = max(0, (int)gg - g) + max(0, (int)yy - y);
            res = min(res, f(r + 1, g, y, 0) + cost);
      }
      if(g < G.size() && l != 1) {
            auto rr = upper_bound(R.begin(), R.end(), G[g]) - R.begin();
            auto yy = upper_bound(Y.begin(), Y.end(), G[g]) - Y.begin();

            int cost = max(0, (int)rr - r) + max(0, (int)yy - y);
            res = min(res, f(r, g + 1, y, 1) + cost);
      }
      if(y < Y.size() && l != 2) {
            auto rr = upper_bound(R.begin(), R.end(), Y[y]) - R.begin();
            auto gg = upper_bound(G.begin(), G.end(), Y[y]) - G.begin();

            int cost = max(0, (int)rr - r) + max(0, (int)gg - g);
            res = min(res, f(r, g, y + 1, 2) + cost);
      }

      // cout << r << " " << g << " " << y << " = " << res << '\n';

      return dp[r][g][y][l] = res;
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      memset(dp, -1, sizeof dp);

      cin >> N >> s;

      for(int i = 0; i < N; i++) {
            if(s[i] == 'R') {
                  R.push_back(i);
            }
            if(s[i] == 'G') {
                  G.push_back(i);
            }
            if(s[i] == 'Y') {
                  Y.push_back(i);
            }
      }

      int k = f(0, 0, 0, 3);
      if(k == 1e9) k = -1;
      cout << k << '\n';
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int f(int, int, int, int)':
joi2019_ho_t3.cpp:17:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |       if(r < R.size() && l != 0) {
      |          ~~^~~~~~~~~~
joi2019_ho_t3.cpp:24:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |       if(g < G.size() && l != 1) {
      |          ~~^~~~~~~~~~
joi2019_ho_t3.cpp:31:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |       if(y < Y.size() && l != 2) {
      |          ~~^~~~~~~~~~

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