oj.uz

Submission #953343

# Submission time Handle Problem Language Result Execution time Memory
953343 2024-03-25T20:38:34 Z OkYqsJJ Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 1009908 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 1009684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 1009684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 583 ms 1009908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 1009684 KB Time limit exceeded
2 Halted 0 ms 0 KB -