제출 #1358026

#제출 시각아이디문제언어결과실행 시간메모리
1358026SulAGrowing Vegetable is Fun 3 (JOI19_ho_t3)C++20
60 / 100
6 ms12152 KiB
#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

int label(char c) { return c == 'R' ? 0 : c == 'Y' ? 1 : 2; }

void chmin(int& x, int y) { x = min(x, y); }

const int N = 100;
int dp[N][N][N][3];


int main() {
    int n; string s; cin >> n >> s;
    vector<int> pos[3];
    for (int i = 0; i < n; i++) {
        pos[label(s[i])].push_back(i);
    }
    int m0 = pos[0].size(), m1 = pos[1].size(), m2 = pos[2].size();
    memset(dp, 0x3f, sizeof dp);
    memset(dp[0][0][0], 0, sizeof dp[0][0][0]);

    int p[3];
    for (p[0] = 0; p[0] <= m0; p[0]++) {
        for (p[1] = 0; p[1] <= m1; p[1]++) {
            for (p[2] = 0; p[2] <= m2; p[2]++) {
                if (p[0] + p[1] + p[2] == m0 + m1 + m2) break;
                for (int l = 0; l < 3; l++) {
                    for (int x = 0; x < 3; x++) {
                        if (x == l || p[x] == pos[x].size()) continue;
                        int y = (x+1) % 3;
                        int z = (y+1) % 3;
                        auto sy = pos[y].begin();
                        auto sz = pos[z].begin();
                        int opers = sy + p[y] - upper_bound(sy, sy + p[y], pos[x][p[x]]);
                        opers +=    sz + p[z] - upper_bound(sz, sz + p[z], pos[x][p[x]]);
                        int np[3] = {p[0], p[1], p[2]};
                        np[x]++;
                        chmin(dp[ np[0] ][ np[1] ][ np[2] ][x], dp[ p[0] ][ p[1] ][ p[2] ][l] + opers);
                        np[x]--;
                    }
                }
            }
        }
    }
    int ans = *min_element(dp[m0][m1][m2], dp[m0][m1][m2] + 3);
    cout << (ans > 400*400*400 ? -1 : ans);
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…