Submission #147157

#	Time	Username	Problem	Language	Result	Execution time	Memory
147157		jh05013	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	219 ms	163072 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dbgv(V) for(auto x:V)cout<<x<<' ';cout<<endl;
#define FOR(a,n) for(int a=0;a<n;a++)
void OJize(){cin.tie(NULL); ios_base::sync_with_stdio(false);}

#define ZZ 401
#define INF 999999
int dp[ZZ][ZZ][ZZ][3];
int acc[3][ZZ];
// (r,g,y) counts, last R/G/B ... +1

vector<int> R, G, Y;
void upd(int r, int g, int y, int prev, int cur){
    // Where is the new vegetable?
    int pos=0, nr=r, ng=g, ny=y;
    if(cur == 0)      pos = R[r], nr++;
    else if(cur == 1) pos = G[g], ng++;
    else              pos = Y[y], ny++;
    // How much was it pushed to the right?
    int rig=0;
    if(cur != 0) rig+= max(0, r-acc[0][pos]);
    if(cur != 1) rig+= max(0, g-acc[1][pos]);
    if(cur != 2) rig+= max(0, y-acc[2][pos]);
    // Where is the desired position?
    int goal = r+g+y;
    int nv = dp[r][g][y][prev] + pos+rig-goal;
    dp[nr][ng][ny][cur] = min(dp[nr][ng][ny][cur], nv);
}

int main(){OJize();
    int n; cin>>n;
    string s; cin>>s;
    FOR(i,n){
        if(i) FOR(j,3) acc[j][i] = acc[j][i-1];
        if(s[i] == 'R')      R.push_back(i), acc[0][i]++;
        else if(s[i] == 'G') G.push_back(i), acc[1][i]++;
        else                 Y.push_back(i), acc[2][i]++;
    }
    int RSZ = R.size(), GSZ = G.size(), YSZ = Y.size();
    FOR(r,RSZ+1) FOR(g,GSZ+1) FOR(y,YSZ+1) FOR(i,3) dp[r][g][y][i] = INF;
    FOR(i,3) dp[0][0][0][i] = 0;

    FOR(r,RSZ+1) FOR(g,GSZ+1) FOR(y,YSZ+1){
        if(r != RSZ) upd(r,g,y,1,0), upd(r,g,y,2,0);
        if(g != GSZ) upd(r,g,y,0,1), upd(r,g,y,2,1);
        if(y != YSZ) upd(r,g,y,0,2), upd(r,g,y,1,2);
    }
    int ans = INF;
    FOR(i, 3) ans = min(ans, dp[RSZ][GSZ][YSZ][i]);
    cout << ((ans == INF)? -1 : ans);
}

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