Submission #522652

#	Time	Username	Problem	Language	Result	Execution time	Memory
522652		Monarchuwu	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	500 ms	925452 KiB

joi2019_ho_t3

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;

const int N = 400 + 2, inf = 0x3f3f3f3f;
int n, a[N];
char s[N];
vector<int> c[3];

int prf[N];
int cost[N][N][N][3];
void prep(int op0, int op1, int op2) {
    for (int i = 0; i <= c[op0].size(); ++i) // xóa i con 0
        for (int j = 0; j <= c[op1].size(); ++j) { // xóa j con 1
            fill(prf + 1, prf + n + 1, 0);
            for (int ii = i; ii < c[op0].size(); ++ii) ++prf[c[op0][ii]];
            for (int jj = j; jj < c[op1].size(); ++jj) ++prf[c[op1][jj]];
            for (int i = 1; i <= n; ++i) prf[i] += prf[i - 1];

            for (int k = 0; k < c[op2].size(); ++k) { // cost nếu xóa con 2 thứ k
                if (op2 == 2)
                    cost[i][j][k][2] = prf[c[2][k]];
                else if (op2 == 1)
                    cost[i][k][j][1] = prf[c[1][k]];
                else
                    cost[k][i][j][0] = prf[c[0][k]];
            }
        }
}

// dp[i][j][k][op] : mincost khi dùng i con 0, j con 1, k con 2, con cuối là op
int dp[N][N][N][3];
void minimize(int &a, int b) { if (a > b) a = b; }
int main() {
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> (s + 1);
    for (int i = 1; i <= n; ++i) {
        a[i] = s[i] == 'R' ? 0 : s[i] == 'G' ? 1 : 2;
        c[a[i]].push_back(i);
    }

    if (max({ c[0].size(), c[1].size(), c[2].size() }) > (n + 1) / 2) {
        cout << "-1\n";
        return 0;
    }

    prep(0, 1, 2);
    prep(0, 2, 1);
    prep(1, 2, 0);

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int cnt = 0, k; cnt < n; ++cnt) {
        for (int i = 0; i <= c[0].size(); ++i)
            for (int j = 0; j <= c[1].size(); ++j) {
                int k = cnt - i - j;
                if (k > c[2].size()) continue;

                minimize(dp[i + 1][j][k][0], min(dp[i][j][k][1], dp[i][j][k][2]) + cost[i][j][k][0]);
                minimize(dp[i][j + 1][k][1], min(dp[i][j][k][0], dp[i][j][k][2]) + cost[i][j][k][1]);
                minimize(dp[i][j][k + 1][2], min(dp[i][j][k][0], dp[i][j][k][1]) + cost[i][j][k][2]);
            }
    }
    int ans(inf);
    minimize(ans, dp[c[0].size()][c[1].size()][c[2].size()][0]);
    minimize(ans, dp[c[0].size()][c[1].size()][c[2].size()][1]);
    minimize(ans, dp[c[0].size()][c[1].size()][c[2].size()][2]);
    cout << ans << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void prep(int, int, int)':
joi2019_ho_t3.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i <= c[op0].size(); ++i) // xóa i con 0
      |                     ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for (int j = 0; j <= c[op1].size(); ++j) { // xóa j con 1
      |                         ~~^~~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:19:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             for (int ii = i; ii < c[op0].size(); ++ii) ++prf[c[op0][ii]];
      |                              ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:20:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |             for (int jj = j; jj < c[op1].size(); ++jj) ++prf[c[op1][jj]];
      |                              ~~~^~~~~~~~~~~~~~~
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 < c[op2].size(); ++k) { // cost nếu xóa con 2 thứ k
      |                             ~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:45:56: warning: comparison of integer expressions of different signedness: 'long unsigned int' and 'int' [-Wsign-compare]
   45 |     if (max({ c[0].size(), c[1].size(), c[2].size() }) > (n + 1) / 2) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:57:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for (int i = 0; i <= c[0].size(); ++i)
      |                         ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j = 0; j <= c[1].size(); ++j) {
      |                             ~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 if (k > c[2].size()) continue;
      |                     ~~^~~~~~~~~~~~~
joi2019_ho_t3.cpp:56:23: warning: unused variable 'k' [-Wunused-variable]
   56 |     for (int cnt = 0, k; cnt < n; ++cnt) {
      |                       ^

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