제출 #1159870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159870		weakweakweak	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	472 ms	809764 KiB

joi2019_ho_t3

// g++ -Wall -Wextra -std=c++17 -o C C.cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
using pii = pair<int,int>;
using pll = pair<ll, ll>;
#define fs first 
#define sc second
#define MP make_pair
#pragma GCC optimize("Ofast")

int n, a[510], dp[410][410][410][3];
int pre[3][450] = {0}, pos[3][450] = {0}, tot[3] = {0};
string s;

int calc (int c0, int c1, int c2, int nxt) {
    int hehe = c0+c1+c2+1;
    vector<int> v = {c0,c1,c2};
    int p = pos[nxt][v[nxt]+1];
    if (p == 0) return dp[0][0][0][0];
    int p1 = p;
    for (int i = 0; i < 3; i++) {
        if (nxt == i) continue;
        if (v[i] <= pre[i][p1]) continue;
        p += v[i] - pre[i][p1];
    }
    // cout << p << '\n';
    return abs(p-hehe);
}


int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') a[i+1] = 0;
        else if (s[i] == 'Y') a[i+1] = 1;
        else a[i+1] = 2;
    }

    for (int i = 1; i <= n; i++) {
        tot[a[i]]++;
        pos[a[i]][tot[a[i]]] = i;
        for (int j = 0; j < 3; j++) pre[j][i] = pre[j][i-1];
        pre[a[i]][i]++;
    }

    memset(dp, 63, sizeof(dp));
    dp[1][1][0][0] = calc(0,0,0, 0);
    dp[1][0][1][1] = calc(0,0,0, 1);
    dp[1][0][0][2] = calc(0,0,0, 2);

    for (int i = 2; i <= n; i++) {
        for (int c0 = min(i-1, tot[0]); c0 >= 0; c0--) {
            for (int c1 = min(i-1-c0, tot[1]); c1 >= 0; c1--) {
                int c2 = i-1 - c0 -c1;
                if (c2 > tot[2]) continue;
                dp[i][c0+1][c1][0] = min(dp[i][c0+1][c1][0], min(dp[i-1][c0][c1][1],dp[i-1][c0][c1][2]) + calc(c0,c1,c2, 0));
                dp[i][c0][c1+1][1] = min(dp[i][c0][c1+1][1], min(dp[i-1][c0][c1][0],dp[i-1][c0][c1][2]) + calc(c0,c1,c2, 1));
                dp[i][c0][c1][2] = min(dp[i][c0][c1][2], min(dp[i-1][c0][c1][0],dp[i-1][c0][c1][1]) + calc(c0,c1,c2, 2));
            }
        }
    }
    // cout << calc(1,0,0,1) << '\n';

    int ans = *min_element(dp[n][tot[0]][tot[1]], dp[n][tot[0]][tot[1]]+3);
    if (ans > n*n) ans = -1;
    cout << ans << '\n';
}

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