Submission #876778

#	Time	Username	Problem	Language	Result	Execution time	Memory
876778		parlimoos	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	1087 ms	476 KiB

joi2019_ho_t3

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define cl clear
#define bg begin
#define lb lower_bound
#define ub upper_bound
#define arr(x) array<int , x>
#define endl '\n'

int n;
deque<int> s;
int dp[400][400][3][3];

int f(deque<int> e , int l , int r , int lel , int rel){
    // cout << l << " " << r << "::\n";
    int res = 0;
    for(int i = l ; i <= r ; i++) e.pb(s[i]);
    int len = r - l + 1;
    if(e[0] != lel or e.back() != rel){
        int i = 0;
        for(; i < len ; i++){
            if(e[i] == lel) break;
        }
        if(i == len) return -1;
        else{
            res = i;
            // cout << " ." << dp[l][r][lel][rel] << " ";
            e.erase(e.bg() + i);
            e.insert(e.bg() , lel);
        }
        i = len - 1;
        for(; i >= 1 ; i--){
            if(e[i] == rel) break;
        }
        if(i == 0 or dp[l][r][lel][rel] == -1) return -1;
        else{
            res += len - i - 1;
            // cout << " ." << dp[l][r][lel][rel] << " ";
            e.erase(e.end() - i - 1);
            e.insert(e.end() , rel);
        }
    }
    if(dp[l][r][lel][rel] != -1){
        bool flag = true;
        for(int i = 0 ; i < len - 1 ; i++){
            if(e[i] == e[i + 1]){
                flag = false;
                break;
            }
        }
        if(!flag){
            deque<int> a , b;
            a.pb(e[0]);
            for(int i = 1 ; i < len ; i++) b.pb(e[i]);
            int mn = (int)1e9;
            for(int c = l ; c < r ; c++){
                for(int i = 0 ; i < 3 ; i++){
                    for(int j = 0 ; j < 3 ; j++){
                        if(i == j) continue;
                        int d1 = f(a , l , c , lel , i) , d2 = f(b , c + 1 , r , j , rel);
                        if(d1 != -1 and d2 != -1) mn = min(mn , d1 + d2);
                    }
                }
                a.pb(b[0]);
                b.pop_front();
            }
            if(mn < (int)1e9) res += mn;
            else res = -1;
        }
    }
    return res;
    // cout << " :: " << dp[l][r][lel][rel] << ";\n";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        char d;
        cin >> d;
        if(d == 'R') s.pb(1);
        else if(d == 'Y') s.pb(2);
        else s.pb(0);
    }

    
    int o = int(1e9);
    for(int lel = 0 ; lel < 3 ; lel++){
        for(int rel = 0 ; rel < 3 ; rel++){
            int d = f(s , 0 , n - 1 , lel , rel);
            if(d != -1) o = min(o , d);
        }
    }
    if(o == (int)1e9) cout << -1;
    else cout << o;
}

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