oj.uz

Submission #367025

# Submission time Handle Problem Language Result Execution time Memory
367025 2021-02-16T04:55:53 Z Lam_lai_cuoc_doi Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
15 / 100
 88 ms 164460 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 4e2 + 5;
const int Inf = 1e9 + 7;
int n;
string s;
int dp[N][N][N][3];
int num[3][3][N][N];
int r[N], g[N], y[N];
int a, b, c;

void Read()
{
    cin >> n >> s;
    s = " " + s;
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == 'R')
            r[++a] = i;
        else if (s[i] == 'G')
            g[++b] = i;
        else
            y[++c] = i;
    }
}

inline void Min(int &x, int y)
{
    if (x > y)
        x = y;
}

void Solve()
{
    for (int i = 1; i <= a; ++i)
    {
        int cnt(0);
        for (int j = 0; j <= b; ++j)
        {
            if (g[j] > r[i])
                ++cnt;
            num[0][1][i][j] = cnt;
        }
        cnt = 0;
        for (int j = 0; j <= c; ++j)
        {
            if (y[j] > r[i])
                ++cnt;
            num[0][2][i][j] = cnt;
        }
    }
    for (int i = 1; i <= b; ++i)
    {
        int cnt(0);
        for (int j = 0; j <= a; ++j)
        {
            if (r[j] > g[i])
                ++cnt;
            num[1][0][i][j] = cnt;
        }
        cnt = 0;
        for (int j = 0; j <= c; ++j)
        {
            if (y[j] > g[i])
                ++cnt;
            num[1][2][i][j] = cnt;
        }
    }
    for (int i = 1; i <= c; ++i)
    {
        int cnt(0);
        for (int j = 0; j <= b; ++j)
        {
            if (g[j] > y[i])
                ++cnt;
            num[2][1][i][j] = cnt;
        }
        cnt = 0;
        for (int j = 0; j <= a; ++j)
        {
            if (r[j] > y[i])
                ++cnt;
            num[2][0][i][j] = cnt;
        }
    }
    for (int i = 0; i <= a; ++i)
        for (int j = 0; j <= b; ++j)
            for (int t = 0; t <= c; ++t)
                dp[i][j][t][0] = dp[i][j][t][1] = dp[i][j][t][2] = Inf;
    dp[0][0][0][0] = dp[0][0][0][1] = dp[0][0][0][2] = 0;
    for (int i = 0; i <= a; ++i)
    {
        for (int j = 0; j <= b; ++j)
            for (int t = 0; t <= c; ++t)
            {
                if (i != 0)
                    dp[i][j][t][0] = min(dp[i - 1][j][t][1], dp[i - 1][j][t][2]) + (r[i] + num[0][1][i][j] + num[0][2][i][t]) - (i + j + t);
                if (j != 0)
                    dp[i][j][t][1] = min(dp[i][j - 1][t][0], dp[i][j - 1][t][2]) + (g[j] + num[1][0][j][i] + num[1][2][j][t]) - (i + j + t);
                if (t != 0)
                    dp[i][j][t][2] = min(dp[i][j][t - 1][0], dp[i][j][t - 1][1]) + (y[t] + num[2][0][t][i] + num[2][1][t][j]) - (i + j + t);
            }
    }
    int ans = min(dp[a][b][c][0], min(dp[a][b][c][1], dp[a][b][c][2]));
    cout << (ans == Inf ? -1 : ans);
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Incorrect 1 ms 508 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Incorrect 1 ms 508 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 84 ms 164460 KB Output is correct
3 Correct 87 ms 163564 KB Output is correct
4 Correct 88 ms 164332 KB Output is correct
5 Correct 85 ms 164332 KB Output is correct
6 Correct 85 ms 164332 KB Output is correct
7 Correct 85 ms 163564 KB Output is correct
8 Correct 87 ms 163692 KB Output is correct
9 Correct 83 ms 162668 KB Output is correct
10 Correct 84 ms 164332 KB Output is correct
11 Correct 87 ms 164332 KB Output is correct
12 Correct 23 ms 44780 KB Output is correct
13 Correct 42 ms 78060 KB Output is correct
14 Correct 59 ms 112492 KB Output is correct
15 Correct 86 ms 164332 KB Output is correct
16 Correct 86 ms 164332 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 628 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 748 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 1 ms 620 KB Output is correct
13 Incorrect 1 ms 508 KB Output isn't correct
14 Halted 0 ms 0 KB -