Submission #953343

#	Time	Username	Problem	Language	Result	Execution time	Memory
953343		OkYqsJJ	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	1068 ms	1009908 KiB

joi2019_ho_t3

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

vector<int> G , R , Y;
int n;
string s; 

int dp[401][401][401][4]; 

int brute(int i , int j , int k , int lst){
    int sz = i + j + k ;
    if (sz == n) return 0;
    if (~dp[i][j][k][lst]) return dp[i][j][k][lst]; 
    int a = 1e8 , b = 1e8 , c = 1e8;
    if (lst != 1 && i < G.size()){
        int x = 0; 
        for (int l = 0 ; l < j ; l++) if (R[l] > G[i]) x++; 
        for (int l = 0 ; l < k ; l++) if (Y[l] > G[i]) x++;
        a = brute(i+1 , j , k , 1) + x ; 
    }
    if (lst != 2 && j < R.size()){
       int x = 0;
       for (int l = 0 ; l < i ; l++) if (G[l] > R[j]) x++;
       for (int l = 0 ; l < k ; l++) if (Y[l] > R[j]) x++; 
       b = brute(i , j+1 , k , 2) + x ;
    }
    if (lst != 3 && k < Y.size()){
        int x = 0;
        for (int l = 0 ; l < i ; l++) if (G[l] > Y[k]) x++;
        for (int l = 0 ; l < j ; l++) if (R[l] > Y[k]) x++; 
        c = brute(i , j , k+1 , 3) + x;
    }
    return dp[i][j][k][lst] = 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); 
    }
    memset(dp , -1 , sizeof dp);
    cout << brute(0 , 0 , 0 , 0);
}   


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: 0 / 5
• Subtask 2: 0 / 55
• Subtask 3: 0 / 15
• Subtask 4: 0 / 25