Submission #542074

#	Time	Username	Problem	Language	Result	Execution time	Memory
542074		PixelCat	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	261 ms	2044 KiB

joi2019_ho_t3

/*       code by the cute PixelCat owo       */
/*   as cute as nacho neko (aka. my wife)!   */
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(1000000007)
#define INF (int)(1000000000000000ll)  // 1e15
#define EPS (1e-6)

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p /= 2;
        b = b * b % mod;
    }
    return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

const int MAXN=410;

vector<int32_t> p[3];
int32_t dp[2][MAXN][MAXN][3];

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n; cin>>n;
    string s; cin>>s;
    For(i,0,2) p[i].eb(-1);
    int cnt[3]={0};
    For(i,1,n){
        int j;
        if(s[i-1]=='R') j=0;
        else if(s[i-1]=='G') j=1;
        else j=2;
        p[j].eb(i);
        cnt[j]++;
    }
    // For(i,0,2) debug(i,cnt[i],p[i]);
    auto cost=[&](int i,int j,int k,int c,int x){
        int ans=0;
        ans+=lower_bound(p[0].begin()+1+i,p[0].end(),p[c][x])
             -p[0].begin()-i-1;
        ans+=lower_bound(p[1].begin()+1+j,p[1].end(),p[c][x])
             -p[1].begin()-j-1;
        ans+=lower_bound(p[2].begin()+1+k,p[2].end(),p[c][x])
             -p[2].begin()-k-1;
        return ans;
    };
    For(i,0,cnt[0]) For(j,0,cnt[1]) For(k,0,cnt[2]) For(end,0,2){
        dp[i&1][j][k][end]=0x3f3f3f3f;
        if(i+j+k==0){
            dp[i&1][j][k][end]=0;
            continue;
        }
        int ii=i&1;
        int i2=!(i&1);
        if(end==0){
            if(!i) continue;
            dp[ii][j][k][end]=min(
                dp[i2][j][k][1],dp[i2][j][k][2]
            )+cost(i,j,k,0,i);
        }else if(end==1){
            if(!j) continue;
            dp[ii][j][k][end]=min(
                dp[ii][j-1][k][0],dp[ii][j-1][k][2]
            )+cost(i,j,k,1,j);
        }else if(end==2){
            if(!k) continue;
            dp[ii][j][k][end]=min(
                dp[ii][j][k-1][0],dp[ii][j][k-1][1]
            )+cost(i,j,k,2,k);
        }
    }
    auto ans=0x3f3f3f3f;
    For(e,0,2) chmin(ans,dp[cnt[0]&1][cnt[1]][cnt[2]][e]);
    if(ans<0x3f3f3f3f) cout<<ans<<"\n";
    else cout<<"-1\n";
    // debug(cost(1,1,1,2,2));
    return 0;
}

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