Submission #818875

#	Time	Username	Problem	Language	Result	Execution time	Memory
818875		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	75 / 100	539 ms	775804 KiB

joi2019_ho_t3

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

const int MX = 405;

int N;
string s;

vector < int > dp[MX][MX][4];

int cnt[MX][3]; //R = 0, G = 1, Y = 2
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][l][y] != -1) return dp[r][g][l][y];

      int res = 1e9;
      if(r < R.size() && l != 0) {
            int cost = max(0, cnt[R[r]][1] - g) + max(0, cnt[R[r]][2] - y);
            res = min(res, f(r + 1, g, y, 0) + cost);
      }
      if(g < G.size() && l != 1) {
            int cost = max(0, cnt[G[g]][0] - r) + max(0, cnt[G[g]][2] - y);
            res = min(res, f(r, g + 1, y, 1) + cost);
      }
      if(y < Y.size() && l != 2) {
            int cost = max(0, cnt[Y[y]][0] - r) + max(0, cnt[Y[y]][1] - g);
            res = min(res, f(r, g, y + 1, 2) + cost);
      }

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

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

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

      cin >> N >> s;

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

            if(i > 0) {
                  cnt[i][0] += cnt[i - 1][0];
                  cnt[i][1] += cnt[i - 1][1];
                  cnt[i][2] += cnt[i - 1][2];
            }
      }

      for(int i = 0; i < MX; i++)
            for(int j = 0; j < MX; j++) 
                  for(int c = 0; c < 4; c++)
                        dp[i][j][c].assign(Y.size() + 1, -1);

      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:20:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |       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:28:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |       if(y < Y.size() && l != 2) {
      |          ~~^~~~~~~~~~

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