Submission #1310210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310210		polishprogrammer	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	240 ms	134704 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> yy, gg, rr;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'Y') yy.pb(i);
        else if (s[i] == 'G') gg.pb(i);
        else rr.pb(i);
    }
    int iy = yy.size(), ig = gg.size(), ir = rr.size();
    vector<vector<vector<vector<int>>>> dp(iy + 1, vector<vector<vector<int>>>(ig + 1, vector<vector<int>>(ir + 1, vector<int>(3, 1e9))));
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;
    for (int y = 0; y <= yy.size(); y++) {
        for (int g = 0; g <= gg.size(); g++) {
            for (int r = 0; r <= rr.size(); r++) {
                int w = y + g + r;
                if (y != 0) {
                    int przed = min(g, int(lower_bound(gg.begin(), gg.end(), yy[y - 1]) - gg.begin()))
                              + min(r, int(lower_bound(rr.begin(), rr.end(), yy[y - 1]) - rr.begin()));
                    int po = w - 1 - przed;
                    int koszt = max(0, yy[y - 1] - (y - 1) - przed);
                    dp[y][g][r][0] = min(dp[y-1][g][r][1], dp[y-1][g][r][2]) + koszt;
                }
                if (g != 0) {
                    int przed = min(y, int(lower_bound(yy.begin(), yy.end(), gg[g - 1]) - yy.begin()))
                              + min(r, int(lower_bound(rr.begin(), rr.end(), gg[g - 1]) - rr.begin()));
                    int po = w - 1 - przed;
                    int koszt = max(0, gg[g - 1] - (g - 1) - przed);
                    dp[y][g][r][1] = min(dp[y][g-1][r][0], dp[y][g-1][r][2]) + koszt;
                }
                if (r != 0) {
                    int przed = min(g, int(lower_bound(gg.begin(), gg.end(), rr[r - 1]) - gg.begin()))
                              + min(y, int(lower_bound(yy.begin(), yy.end(), rr[r - 1]) - yy.begin()));
                    int po = w - 1 - przed;
                    int koszt = max(0, rr[r - 1] - (r - 1) - przed);
                    dp[y][g][r][2] = min(dp[y][g][r-1][0], dp[y][g][r-1][1]) + koszt;
                }
            }
        }
    }
    int wyn = min(dp[iy][ig][ir][0], min(dp[iy][ig][ir][1], dp[iy][ig][ir][2]));
    if (wyn >= 1e9) cout << -1;
    else cout << wyn;
}

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