제출 #1139492

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1139492		VMaksimoski008	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	75 / 100	502 ms	164168 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

ll dp[405][405][405][3];

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    int n; cin >> n;
    string s; cin >> s;
    vector<int> a(n+1), vec[3];

    for(int i=0; i<n; i++) {
        int val = 0;
        if(s[i] == 'G') val = 1;
        if(s[i] == 'Y') val = 2;
        a[i+1] = val;
        vec[val].push_back(i+1);
    }

    vector<int> sz(3);
    for(int i=0; i<3; i++) sz[i] = vec[i].size();
    for(int i=0; i<=sz[0]; i++)
        for(int j=0; j<=sz[1]; j++)
            for(int k=0; k<=sz[2]; k++)
                for(int x=0; x<3; x++) dp[i][j][k][x] = 1e18;
    for(int i=0; i<3; i++) dp[0][0][0][i] = 0;

    vector<int> it(3);
    for(it[0]=0; it[0]<=sz[0]; it[0]++) {
        for(it[1]=0; it[1]<=sz[1]; it[1]++) {
            for(it[2]=0; it[2]<=sz[2]; it[2]++) {
                for(int x=0; x<3; x++) {
                    if(!it[x]) continue;
                    for(int lst=0; lst<3; lst++) {
                        if(x == lst) continue;
                        int p = vec[x][it[x]-1];
                        ll cost = 0;
                        
                        for(int y=0; y<3; y++) {
                            if(x == y) continue;
                            cost += max(0, int(lower_bound(vec[y].begin(), vec[y].end(), p) - vec[y].begin()) - it[y]);
                        }

                        vector<int> it2 = it;
                        it2[x]--;
                        dp[it[0]][it[1]][it[2]][x] = min(dp[it[0]][it[1]][it[2]][x], dp[it2[0]][it2[1]][it2[2]][lst] + cost);
                    }
                }
            }
        }
    }

    ll ans = 1e18;
    for(int i=0; i<3; i++) ans = min(ans, dp[sz[0]][sz[1]][sz[2]][i]);
    cout << (ans < 1e18 ? ans : -1) << '\n';
}

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