oj.uz

Submission #522652

# Submission time Handle Problem Language Result Execution time Memory
522652 2022-02-05T10:09:23 Z Monarchuwu Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
100 / 100
 500 ms 925452 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 763100 KB Output is correct
2 Correct 310 ms 763084 KB Output is correct
3 Correct 325 ms 763064 KB Output is correct
4 Correct 311 ms 763132 KB Output is correct
5 Correct 299 ms 763148 KB Output is correct
6 Correct 307 ms 763328 KB Output is correct
7 Correct 317 ms 763316 KB Output is correct
8 Correct 310 ms 763148 KB Output is correct
9 Correct 310 ms 763412 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 314 ms 763244 KB Output is correct
12 Correct 335 ms 763220 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 299 ms 763248 KB Output is correct
15 Correct 293 ms 763172 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 308 KB Output is correct

Subtask #2
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 763100 KB Output is correct
2 Correct 310 ms 763084 KB Output is correct
3 Correct 325 ms 763064 KB Output is correct
4 Correct 311 ms 763132 KB Output is correct
5 Correct 299 ms 763148 KB Output is correct
6 Correct 307 ms 763328 KB Output is correct
7 Correct 317 ms 763316 KB Output is correct
8 Correct 310 ms 763148 KB Output is correct
9 Correct 310 ms 763412 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 314 ms 763244 KB Output is correct
12 Correct 335 ms 763220 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 299 ms 763248 KB Output is correct
15 Correct 293 ms 763172 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 285 ms 765008 KB Output is correct
19 Correct 291 ms 764640 KB Output is correct
20 Correct 277 ms 765004 KB Output is correct
21 Correct 285 ms 765216 KB Output is correct
22 Correct 278 ms 764456 KB Output is correct
23 Correct 307 ms 764796 KB Output is correct
24 Correct 279 ms 764384 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 291 ms 765764 KB Output is correct
28 Correct 297 ms 765120 KB Output is correct
29 Correct 336 ms 764992 KB Output is correct
30 Correct 282 ms 765016 KB Output is correct
31 Correct 289 ms 764740 KB Output is correct
32 Correct 296 ms 765264 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 328 KB Output is correct
35 Correct 312 ms 765428 KB Output is correct
36 Correct 318 ms 764612 KB Output is correct
37 Correct 332 ms 764408 KB Output is correct
38 Correct 294 ms 764908 KB Output is correct
39 Correct 293 ms 765092 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 763060 KB Output is correct
2 Correct 493 ms 925328 KB Output is correct
3 Correct 476 ms 924612 KB Output is correct
4 Correct 493 ms 925384 KB Output is correct
5 Correct 450 ms 925324 KB Output is correct
6 Correct 473 ms 925444 KB Output is correct
7 Correct 468 ms 924608 KB Output is correct
8 Correct 500 ms 924648 KB Output is correct
9 Correct 451 ms 923812 KB Output is correct
10 Correct 452 ms 925368 KB Output is correct
11 Correct 441 ms 925452 KB Output is correct
12 Correct 347 ms 806740 KB Output is correct
13 Correct 373 ms 839784 KB Output is correct
14 Correct 403 ms 873880 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 0 ms 204 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 763100 KB Output is correct
2 Correct 310 ms 763084 KB Output is correct
3 Correct 325 ms 763064 KB Output is correct
4 Correct 311 ms 763132 KB Output is correct
5 Correct 299 ms 763148 KB Output is correct
6 Correct 307 ms 763328 KB Output is correct
7 Correct 317 ms 763316 KB Output is correct
8 Correct 310 ms 763148 KB Output is correct
9 Correct 310 ms 763412 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 314 ms 763244 KB Output is correct
12 Correct 335 ms 763220 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 299 ms 763248 KB Output is correct
15 Correct 293 ms 763172 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 308 KB Output is correct
18 Correct 285 ms 765008 KB Output is correct
19 Correct 291 ms 764640 KB Output is correct
20 Correct 277 ms 765004 KB Output is correct
21 Correct 285 ms 765216 KB Output is correct
22 Correct 278 ms 764456 KB Output is correct
23 Correct 307 ms 764796 KB Output is correct
24 Correct 279 ms 764384 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 291 ms 765764 KB Output is correct
28 Correct 297 ms 765120 KB Output is correct
29 Correct 336 ms 764992 KB Output is correct
30 Correct 282 ms 765016 KB Output is correct
31 Correct 289 ms 764740 KB Output is correct
32 Correct 296 ms 765264 KB Output is correct
33 Correct 1 ms 204 KB Output is correct
34 Correct 1 ms 328 KB Output is correct
35 Correct 312 ms 765428 KB Output is correct
36 Correct 318 ms 764612 KB Output is correct
37 Correct 332 ms 764408 KB Output is correct
38 Correct 294 ms 764908 KB Output is correct
39 Correct 293 ms 765092 KB Output is correct
40 Correct 0 ms 204 KB Output is correct
41 Correct 0 ms 204 KB Output is correct
42 Correct 328 ms 763060 KB Output is correct
43 Correct 493 ms 925328 KB Output is correct
44 Correct 476 ms 924612 KB Output is correct
45 Correct 493 ms 925384 KB Output is correct
46 Correct 450 ms 925324 KB Output is correct
47 Correct 473 ms 925444 KB Output is correct
48 Correct 468 ms 924608 KB Output is correct
49 Correct 500 ms 924648 KB Output is correct
50 Correct 451 ms 923812 KB Output is correct
51 Correct 452 ms 925368 KB Output is correct
52 Correct 441 ms 925452 KB Output is correct
53 Correct 347 ms 806740 KB Output is correct
54 Correct 373 ms 839784 KB Output is correct
55 Correct 403 ms 873880 KB Output is correct
56 Correct 1 ms 204 KB Output is correct
57 Correct 0 ms 204 KB Output is correct
58 Correct 492 ms 838452 KB Output is correct
59 Correct 471 ms 858688 KB Output is correct
60 Correct 481 ms 849996 KB Output is correct
61 Correct 461 ms 847088 KB Output is correct
62 Correct 0 ms 204 KB Output is correct
63 Correct 442 ms 922760 KB Output is correct
64 Correct 449 ms 912636 KB Output is correct
65 Correct 454 ms 901156 KB Output is correct
66 Correct 453 ms 848252 KB Output is correct
67 Correct 467 ms 845156 KB Output is correct
68 Correct 465 ms 850844 KB Output is correct
69 Correct 455 ms 847556 KB Output is correct
70 Correct 475 ms 854596 KB Output is correct
71 Correct 475 ms 846036 KB Output is correct
72 Correct 1 ms 204 KB Output is correct
73 Correct 1 ms 324 KB Output is correct