제출 #253556

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
253556		Atill83	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	256 ms	97548 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 405;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n;
string s;
deque<int> ves[MAXN];
pii say[MAXN];
int pre[MAXN][3];
int yer[3][MAXN];
int dp[202][202][202][3];


int d(int r, int g, int y, int st){
    if(r < 0 || g < 0 || y < 0) return mod;
    if(r + g + y == 0) return 0;
    int &ans = dp[r][g][y][st];
    if(ans != -1){
        return ans;
    }

    ans = mod;

    if(st == 0){
        int yr = yer[st][r];
        int rr = min(r, pre[yr][0]);
        int gg = min(g, pre[yr][1]);
        int yy = min(y, pre[yr][2]);
        ans = min(ans, d(r - 1, g, y, 1) + max(0, yr - rr - gg - yy));
        ans = min(ans, d(r - 1, g, y, 2) + max(0, yr - rr - gg - yy));
    }else if(st == 1){
        
        int yr = yer[st][g];
        int rr = min(r, pre[yr][0]);
        int gg = min(g, pre[yr][1]);
        int yy = min(y, pre[yr][2]);
        ans = min(ans, d(r, g - 1, y, 0) + max(0, yr - rr - gg - yy));
        ans = min(ans, d(r, g - 1, y, 2) + max(0, yr - rr - gg - yy));
    }else {
        
        int yr = yer[st][y];
        int rr = min(r, pre[yr][0]);
        int gg = min(g, pre[yr][1]);
        int yy = min(y, pre[yr][2]);
        ans = min(ans, d(r, g, y - 1, 0) + max(0, yr - rr - gg - yy));
        ans = min(ans, d(r, g, y - 1, 1) + max(0, yr - rr - gg - yy));
    }
    return ans;
}












int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif
    memset(dp, -1, sizeof(dp));
    cin>>n>>s;
    int r = 0, g = 0, y = 0;
    int idx = 1;
    for(char i: s){
        if(i == 'R'){ 
            pre[idx][0]++;
            r++;
            yer[0][r] = idx;
        }else if(i == 'G'){
            pre[idx][1]++;
            g++;
            yer[1][g] = idx;
        }else{ 
            pre[idx][2]++;
            y++;
            yer[2][y] = idx;
        }
        if(idx)
            pre[idx][0] += pre[idx - 1][0], pre[idx][1] += pre[idx - 1][1], pre[idx][2] += pre[idx - 1][2];
        idx++;
    }

        

    if(max({r, g, y}) > (n + 1) / 2) {
        cout<<-1<<endl;
        return 0;
    }

    

    cout<<min({d(r, g, y, 0), d(r, g, y, 1), d(r, g , y, 2)});







    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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