Submission #629622

#	Time	Username	Problem	Language	Result	Execution time	Memory
629622		Abrar_Al_Samit	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	408 ms	98632 KiB

joi2019_ho_t3

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

const int INF = 1e9;

const int MX = 203;

int n;
int dp[MX][MX][MX][3];

vector<int>id[3]; //R G Y

int solve(int r, int g, int y, int prev) {
  if(r+g+y==n) return 0;
  int &ret = dp[r][g][y][prev];
  if(ret!=-1) return ret;
  ret = INF;


  auto fix = [&] (int &a) {
    a = max(0, a);
  };

  if(r+g+y==0 || prev!=0) {
    if(id[0].size()>r) {
      int cost1 = upper_bound(id[1].begin(), id[1].end(), id[0][r]) - id[1].begin();
      cost1 -= g;
      int cost2 = upper_bound(id[2].begin(), id[2].end(), id[0][r]) - id[2].begin();
      cost2 -= y;
      fix(cost1);      
      fix(cost2);
      ret = min(ret, cost1+cost2+solve(r+1, g, y, 0));
    }
  }
  if(prev!=1 && id[1].size()>g) {
    int cost1 = upper_bound(id[0].begin(), id[0].end(), id[1][g]) - id[0].begin();
    cost1 -= r;
    int cost2 = upper_bound(id[2].begin(), id[2].end(), id[1][g]) - id[2].begin();
    cost2 -= y;
    fix(cost1);      
    fix(cost2);
    ret = min(ret, cost1+cost2+solve(r, g+1, y, 1));
  }
  if(prev!=2 && id[2].size()>y) {
    int cost1 = upper_bound(id[0].begin(), id[0].end(), id[2][y]) - id[0].begin();
    cost1 -= r;
    int cost2 = upper_bound(id[1].begin(), id[1].end(), id[2][y]) - id[1].begin();
    cost2 -= g;
    fix(cost1);      
    fix(cost2);
    ret = min(ret, cost1+cost2+solve(r, g, y+1, 2));
  }
  return ret;
}
void PlayGround() {
  string s;
  cin>>n>>s;
  for(int i=0; i<n; ++i) {
    if(s[i]=='R') id[0].push_back(i);
    else if(s[i]=='G') id[1].push_back(i);
    else id[2].push_back(i);
  }
  int mx = max({id[0].size(), id[1].size(), id[2].size()});
  if((n+1)/2<mx) {
    cout<<"-1\n";
    return;
  }
  memset(dp, -1, sizeof dp);
  cout<<solve(0, 0, 0, 0)<<'\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  PlayGround();
  return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int solve(int, int, int, int)':
joi2019_ho_t3.cpp:25:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     if(id[0].size()>r) {
      |        ~~~~~~~~~~~~^~
joi2019_ho_t3.cpp:35:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |   if(prev!=1 && id[1].size()>g) {
      |                 ~~~~~~~~~~~~^~
joi2019_ho_t3.cpp:44:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |   if(prev!=2 && id[2].size()>y) {
      |                 ~~~~~~~~~~~~^~

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