oj.uz

Submission #676407

# Submission time Handle Problem Language Result Execution time Memory
676407 2022-12-30T18:16:43 Z stevancv Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 8 ms 3816 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 1e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    vector<int> x, y, z;
    x.push_back(-1);
    y.push_back(-1);
    z.push_back(-1);
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') x.push_back(i);
        if (s[i] == 'G') y.push_back(i);
        if (s[i] == 'Y') z.push_back(i);
    }
    int X = x.size();
    int Y = y.size();
    int Z = z.size();
    vector<vector<vector<vector<int>>>> dp(X);
    for (int i = 0; i < X; i++) {
        dp[i].resize(Y);
        for (int j = 0; j < Y; j++) {
            dp[i][j].resize(Z, vector<int>(3, inf));
        }
    }
    for (int l = 0; l < 3; l++) dp[0][0][0][l] = 0;
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            for (int k = 0; k < Z; k++) {
                int pos = i + j + k - 1;
                if (i > 0) dp[i][j][k][0] = min(dp[i - 1][j][k][1], dp[i - 1][j][k][2]) + max(0, x[i] - pos);
                if (j > 0) dp[i][j][k][1] = min(dp[i][j - 1][k][0], dp[i][j - 1][k][2]) + max(0, y[j] - pos);
                if (k > 0) dp[i][j][k][2] = min(dp[i][j][k - 1][0], dp[i][j][k - 1][1]) + max(0, z[k] - pos);
            }
        }
    }
    int ans = inf;
    for (int l = 0; l < 3; l++) smin(ans, dp[X - 1][Y - 1][Z - 1][l]);
    if (ans == inf) ans = -1;
    cout << ans << en;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 6 ms 3776 KB Output is correct
3 Correct 6 ms 3796 KB Output is correct
4 Correct 6 ms 3796 KB Output is correct
5 Correct 8 ms 3816 KB Output is correct
6 Correct 6 ms 3796 KB Output is correct
7 Correct 6 ms 3668 KB Output is correct
8 Correct 6 ms 3784 KB Output is correct
9 Correct 8 ms 3668 KB Output is correct
10 Correct 6 ms 3796 KB Output is correct
11 Correct 7 ms 3728 KB Output is correct
12 Correct 4 ms 1236 KB Output is correct
13 Correct 4 ms 1876 KB Output is correct
14 Correct 4 ms 2644 KB Output is correct
15 Correct 7 ms 3800 KB Output is correct
16 Correct 6 ms 3796 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 316 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Incorrect 1 ms 212 KB Output isn't correct
12 Halted 0 ms 0 KB -