Submission #879157

#	Time	Username	Problem	Language	Result	Execution time	Memory
879157		niter	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	277 ms	485096 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define ins isnert
#define pii pair<int,int>
#define ff first
#define ss second
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define spac cerr << ' ';
#define entr cerr << endl;
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x << " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) (x).begin(), (x).end()
using namespace std;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());

int a[405], cnt[3];
vector<int> pos[3];
int dp[405][405][405][3], pref[405][3];
int from[405][405][405][3];
bool vis[405][405][405][3];
const int INF = 1e8;

inline void upd(int &x, int y){
    x = min(x, y);
}
inline int pos_diff(int ca, int cb, int cc, int last){
    int now = ca + cb + cc - 1; // 0-based
    if(last == 0){
        return max(pref[pos[0][ca]][1] - cb, 0) + max(pref[pos[0][ca]][2] - cc, 0);
    }
    if(last == 1){
        return max(pref[pos[1][cb]][0] - ca, 0) + max(pref[pos[1][cb]][2] - cc, 0);
    }
    if(last == 2){
        return max(pref[pos[2][cc]][0] - ca, 0) + max(pref[pos[2][cc]][1] - cb, 0);
    }
}
int cac(int ca, int cb, int cc, int last){
    if(ca < 0 || cb < 0 || cc < 0) return INF;
    if(ca == 0 && cb == 0 && cc == 0) return 0;
    if(last == 0 && ca == 0) return INF;
    if(last == 1 && cb == 0) return INF;
    if(last == 2 && cc == 0) return INF;
    if(vis[ca][cb][cc][last]) return dp[ca][cb][cc][last];
    loop(i,0,3){
        if(i == last) continue;
        int ret = cac(ca-(last == 0), cb-(last == 1), cc-(last == 2), i) + pos_diff(ca, cb, cc, last);
//        if(ca == 5)
//        if(cb == 7)
//        if(cc == 3)
//        if(i == 2){
//            op(ret)
//            op(ca - ((last) == 0))
//            op(cb - ((last) == 1))
//            op(cc - ((last) == 2))
//            op(dp[ca-(last == 0)][cb-(last == 1)][cc-(last == 2)][i])
//        }
        upd(dp[ca][cb][cc][last], ret);
        if(dp[ca][cb][cc][last] == ret) from[ca][cb][cc][last] = i;
    }
    vis[ca][cb][cc][last] = true;
    if(dp[ca][cb][cc][last] >= INF) from[ca][cb][cc][last] = -1;
    return dp[ca][cb][cc][last];
}

void trans(int ca, int cb, int cc, int la){
    if(ca + cb + cc == 0) return;
    int fr = from[ca][cb][cc][la];
    trans(ca - (la == 0), cb - (la == 1), cc - (la == 2), fr);
    opa(ca) opa(cb) opa(cc) opa(la)
    op(dp[ca][cb][cc][la])
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
//    freopen("in.txt", "r", stdin);
    int n; string s;
    cin >> n >> s;
    loop(i,0,3) pos[i].pb(-999);
    loop(i,0,n){
        if(s[i] == 'R') a[i] = 0;
        else if(s[i] == 'G') a[i] = 1;
        else a[i] = 2;
        cnt[a[i]]++;
        pos[a[i]].pb(i);
        pref[i][a[i]]++;
        if(i != 0) loop(j,0,3){
            pref[i][j] += pref[i-1][j];
        }
    }
//    loop(i,0,3){
//        opa(i) STL(pos[i])
//    }
    loop(i,0,cnt[0]+1)
        loop(j,0,cnt[1]+1)
            loop(k,0,cnt[2]+1)
                loop(l,0,3)
                    dp[i][j][k][l] = INF;
    loop(i,0,3){
        vis[0][0][0][i] = true;
        dp[0][0][0][i] = 0;
    }
    int ans = INF;
    loop(i,0,3){
        if(cnt[i] != 0){
            cac(cnt[0], cnt[1], cnt[2], i);
            ans = min(ans, dp[cnt[0]][cnt[1]][cnt[2]][i]);
//            opa(i) op(dp[cnt[0]][cnt[1]][cnt[2]][i])
        }
    }
//    trans(cnt[0], cnt[1], cnt[2], from[cnt[0]][cnt[1]][cnt[2]][2]);
    if(ans == INF) cout << "-1\n";
    else cout << ans << '\n';
}
/*
222000001111111

212010101010121
*/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int pos_diff(int, int, int, int)':
joi2019_ho_t3.cpp:30:9: warning: unused variable 'now' [-Wunused-variable]
   30 |     int now = ca + cb + cc - 1; // 0-based
      |         ^~~
joi2019_ho_t3.cpp:40:1: warning: control reaches end of non-void function [-Wreturn-type]
   40 | }
      | ^

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