Submission #375992

#	Time	Username	Problem	Language	Result	Execution time	Memory
375992		valerikk	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	443 ms	792196 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 407;
const int INF = 0x3f3f3f3f;

int dp[N][N][N][3];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> r, g, y;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'R')
            r.push_back(i);
        if (s[i] == 'G')
            g.push_back(i);
        if (s[i] == 'Y')
            y.push_back(i);
    }
    vector<int> rposg, rposy;
    vector<int> gposr, gposy;
    vector<int> yposr, yposg;
    for (int i = 0; i < r.size(); ++i) {
        rposg.push_back(upper_bound(g.begin(), g.end(), r[i]) - g.begin());
        rposy.push_back(upper_bound(y.begin(), y.end(), r[i]) - y.begin());
    }
    for (int i = 0; i < g.size(); ++i) {
        gposr.push_back(upper_bound(r.begin(), r.end(), g[i]) - r.begin());
        gposy.push_back(upper_bound(y.begin(), y.end(), g[i]) - y.begin());
    }
    for (int i = 0; i < y.size(); ++i) {
        yposr.push_back(upper_bound(r.begin(), r.end(), y[i]) - r.begin());
        yposg.push_back(upper_bound(g.begin(), g.end(), y[i]) - g.begin());
    }
    int red = r.size(), green = g.size(), yellow = y.size();
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 0; i < 3; ++i)
        dp[0][0][0][i] = 0;
    for (int i = 0; i <= red; ++i) {
        for (int j = 0; j <= green; ++j) {
            for (int k = 0; k <= yellow; ++k) {
                for (int last = 0; last < 3; ++last) {
                    int val = dp[i][j][k][last];
                    if (val == INF)
                        continue;
                    if (i < red && last != 0) dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], val + max(0, j - rposg[i]) + max(0, k - rposy[i]));
                    if (j < green && last != 1) dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], val + max(0, i - gposr[j]) + max(0, k - gposy[j]));
                    if (k < yellow && last != 2) dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2], val + max(0, i - yposg[k]) + max(0, j - yposg[k]));
                }
            }
        }
    }
    int ans = INF;
    for (int i = 0; i < 3; ++i)
        ans = min(ans, dp[red][green][yellow][i]);
    if (ans == INF) {
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < r.size(); ++i) {
      |                     ~~^~~~~~~~~~
joi2019_ho_t3.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < g.size(); ++i) {
      |                     ~~^~~~~~~~~~
joi2019_ho_t3.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < y.size(); ++i) {
      |                     ~~^~~~~~~~~~

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