Submission #953358

#	Time	Username	Problem	Language	Result	Execution time	Memory
953358		OkYqsJJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	358 ms	41308 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
 
vector<int> G , R , Y;
int n;
string s; 
 
vector<vector<vector<int>>> dp[4];
 
int brute(int i , int j , int k , int lst){
    int sz = i + j + k ;
    if (sz == n) return 0;
    if (~dp[lst][i][j][k]) return dp[lst][i][j][k]; 
    int a = 1e8 , b = 1e8 , c = 1e8;
    if (lst != 1 && i < G.size()){
        int x = upper_bound(R.begin() , R.begin() + j , G[i]) - R.begin();
        int y = upper_bound(Y.begin() , Y.begin() + k , G[i]) - Y.begin();
        x =  j-x; y = k-y; 
        a = brute(i+1 , j , k , 1) + x + y; 
    }
    if (lst != 2 && j < R.size()){
       int x = upper_bound(G.begin() , G.begin() + i , R[j]) - G.begin();
       int y = upper_bound(Y.begin() , Y.begin() + k , R[j]) - Y.begin();
       x =  i-x; y = k-y; 
       b = brute(i , j+1 , k , 2) + x + y;
    }
    if (lst != 3 && k < Y.size()){
       int x = upper_bound(G.begin() , G.begin() + i , Y[k]) - G.begin();
       int y = upper_bound(R.begin() , R.begin() + j , Y[k]) - R.begin();
       x =  i-x; y = j-y; 
       c = brute(i , j , k+1 , 3) + x + y;
    }
    return dp[lst][i][j][k]= min({a , b , c});
}
 
void doWork(){
    cin >> n >> s;
    for (int i = 0 ; i < n ; i++){
        if (s[i] == 'G') G.push_back(i);
        else if (s[i] == 'R') R.push_back(i);
        else Y.push_back(i); 
    }

    for (int i = 0 ; i < 4 ; i++){
        dp[i].resize(G.size() + 1);
        for (auto &j : dp[i]) 
        { j.resize(R.size()+1);  for (auto &k : j) k.resize(Y.size()+1 , -1);  }
    } 

    int ans =  brute(0 , 0 , 0 , 0);
    cout << (ans == 1e8 ? -1 : ans) ;
}   
 
 
signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    doWork(); 
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int brute(int, int, int, int)':
joi2019_ho_t3.cpp:15:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     if (lst != 1 && i < G.size()){
      |                     ~~^~~~~~~~~~
joi2019_ho_t3.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (lst != 2 && j < R.size()){
      |                     ~~^~~~~~~~~~
joi2019_ho_t3.cpp:27:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     if (lst != 3 && k < Y.size()){
      |                     ~~^~~~~~~~~~

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