oj.uz

Submission #375992

# Submission time Handle Problem Language Result Execution time Memory
375992 2021-03-10T14:39:39 Z valerikk Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 443 ms 792196 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 425 ms 791916 KB Output is correct
2 Incorrect 422 ms 791916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 791916 KB Output is correct
2 Incorrect 422 ms 791916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 792044 KB Output is correct
2 Correct 411 ms 792196 KB Output is correct
3 Correct 418 ms 791916 KB Output is correct
4 Correct 414 ms 791916 KB Output is correct
5 Correct 443 ms 792060 KB Output is correct
6 Correct 408 ms 791916 KB Output is correct
7 Correct 421 ms 792044 KB Output is correct
8 Correct 412 ms 791916 KB Output is correct
9 Correct 414 ms 792044 KB Output is correct
10 Correct 411 ms 792032 KB Output is correct
11 Correct 411 ms 791916 KB Output is correct
12 Correct 412 ms 792172 KB Output is correct
13 Correct 430 ms 791916 KB Output is correct
14 Correct 414 ms 792044 KB Output is correct
15 Correct 407 ms 792044 KB Output is correct
16 Correct 434 ms 792172 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 791916 KB Output is correct
2 Incorrect 422 ms 791916 KB Output isn't correct
3 Halted 0 ms 0 KB -