Submission #366094

#	Time	Username	Problem	Language	Result	Execution time	Memory
366094		dolphingarlic	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	90 ms	163072 KiB

joi2019_ho_t3

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

const int INF = 1e6;

vector<int> has[4];
int dp[401][401][401][4];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        if (c == 'R') has[1].push_back(i);
        if (c == 'G') has[2].push_back(i);
        if (c == 'Y') has[3].push_back(i);
    }
    dp[0][0][0][1] = dp[0][0][0][2] = dp[0][0][0][3] = 0;
    for (int i = 0; i <= has[1].size(); i++)
        for (int j = 0; j <= has[2].size(); j++)
            for (int k = 0; k <= has[3].size(); k++) {
                if (i || j || k) dp[i][j][k][1] = dp[i][j][k][2] = dp[i][j][k][3] = INF;
                int tot = i + j + k;
                if (i) dp[i][j][k][1] = min(dp[i - 1][j][k][2], dp[i - 1][j][k][3]) + max(0, has[1][i - 1] - tot);
                if (j) dp[i][j][k][2] = min(dp[i][j - 1][k][1], dp[i][j - 1][k][3]) + max(0, has[2][j - 1] - tot);
                if (k) dp[i][j][k][3] = min(dp[i][j][k - 1][1], dp[i][j][k - 1][2]) + max(0, has[3][k - 1] - tot);
            }
    int ans = *min_element(dp[has[1].size()][has[2].size()][has[3].size()] + 1, dp[has[1].size()][has[2].size()][has[3].size()] + 4);
    if (ans >= INF) cout << -1;
    else cout << ans;
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (int i = 0; i <= has[1].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int j = 0; j <= has[2].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:23:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             for (int k = 0; k <= has[3].size(); k++) {
      |                             ~~^~~~~~~~~~~~~~~~

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