Submission #366122

#	Time	Username	Problem	Language	Result	Execution time	Memory
366122		tushar_2658	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	464 ms	780524 KiB

joi2019_ho_t3

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

const int maxn = 405;

int dp[maxn][maxn][maxn][3];
vector<int> inp[3];
int prv[3][maxn], a[maxn];

int main(int argc, char const *argv[])
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  string s;
  cin >> s;
  for(int i = 0; i < n; ++i){
    if(s[i] == 'R')a[i] = 0;
    else if(s[i] == 'G')a[i] = 1;
    else a[i] = 2;
  }
  for(int i = 0; i < n; ++i){
    inp[a[i]].push_back(i);
    for(int j = 0; j < 3; ++j){
      prv[j][i] = inp[j].size();
    }
  }
  memset(dp, 63, sizeof dp);
  for(int i = 0; i < 3; ++i){
    dp[0][0][0][i] = 0;
  }
  for(int a = 0; a <= (int)inp[0].size(); ++a){
    for(int b = 0; b <= (int)inp[1].size(); ++b){
      for(int c = 0; c <= (int)inp[2].size(); ++c){
        for(int last = 0; last < 3; ++last){
          if(last != 0 && a + 1 <= inp[0].size()){
            int pos = inp[0][a];
            int mn = dp[a][b][c][last] + max(0, prv[1][pos] - b) + max(0, prv[2][pos] - c);
            dp[a + 1][b][c][0] = min(dp[a + 1][b][c][0], mn);
          }
          if(last != 1 && b + 1 <= inp[1].size()){
            int pos = inp[1][b];
            int mn = dp[a][b][c][last] + max(0, prv[0][pos] - a) + max(0, prv[2][pos] - c);
            dp[a][b + 1][c][1] = min(dp[a][b + 1][c][1], mn);
          }
          if(last != 2 && c + 1 <= inp[2].size()){
            int pos = inp[2][c];
            int mn = dp[a][b][c][last] + max(0, prv[0][pos] - a) + max(0, prv[1][pos] - b);
            dp[a][b][c + 1][2] = min(dp[a][b][c + 1][2], mn);
          }
        }
      }
    }
  }
  int ans = 1e8;
  for(int i = 0; i < 3; ++i){
    ans = min(ans, dp[(int)inp[0].size()][(int)inp[1].size()][(int)inp[2].size()][i]);
  }
  if(ans == 1e8){
    cout << "-1" << '\n';
  }else {
    cout << ans << '\n';
  }

  return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main(int, const char**)':
joi2019_ho_t3.cpp:38:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |           if(last != 0 && a + 1 <= inp[0].size()){
      |                           ~~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:43:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |           if(last != 1 && b + 1 <= inp[1].size()){
      |                           ~~~~~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:48:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |           if(last != 2 && c + 1 <= inp[2].size()){
      |                           ~~~~~~^~~~~~~~~~~~~~~~

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