oj.uz

Submission #1086681

# Submission time Handle Problem Language Result Execution time Memory
1086681 2024-09-11T09:02:05 Z _callmelucian Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 43 ms 97112 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

int dp[3][404][202][202];
int pr[404], pg[404], py[404];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, cr = 0, cg = 0, cy = 0; cin >> n;
    for (int i = 1; i <= n; i++) {
        char c; cin >> c;
        if (c == 'R') pr[++cr] = i;
        else if (c == 'G') pg[++cg] = i;
        else py[++cy] = i;
    }

    if (cg < cy)
        swap(cg, cy), swap(pg, py);
    if (cr < cg)
        swap(cr, cg), swap(pr, pg);

    for (int last = 0; last < 3; last++)
        for (int i = 0; i <= cr; i++)
            for (int j = 0; j <= cg; j++)
                for (int k = 0; k <= cy; k++)
                    dp[last][i][j][k] = INT_MAX;

    dp[0][0][0][0] = dp[1][0][0][0] = dp[2][0][0][0] = 0;

    function<void(int,int,int,int)> refine = [&] (int i, int j, int k, int last) {
        int cur = i + j + k;
        if (last == 0) {
            if (i > 0 && dp[1][i - 1][j][k] != INT_MAX)
                dp[0][i][j][k] = min(dp[0][i][j][k], dp[1][i - 1][j][k] + abs(cur - pr[i]));
            if (i > 0 && dp[2][i - 1][j][k] != INT_MAX)
                dp[0][i][j][k] = min(dp[0][i][j][k], dp[2][i - 1][j][k] + abs(cur - pr[i]));
        }
        else if (last == 1) {
            if (j > 0 && dp[0][i][j - 1][k] != INT_MAX)
                dp[1][i][j][k] = min(dp[1][i][j][k], dp[0][i][j - 1][k] + abs(cur - pg[j]));
            if (j > 0 && dp[2][i][j - 1][k] != INT_MAX)
                dp[1][i][j][k] = min(dp[1][i][j][k], dp[2][i][j - 1][k] + abs(cur - pg[j]));
        }
        else {
            if (k > 0 && dp[0][i][j][k - 1] != INT_MAX)
                dp[2][i][j][k] = min(dp[2][i][j][k], dp[0][i][j][k - 1] + abs(cur - py[k]));
            if (k > 0 && dp[1][i][j][k - 1] != INT_MAX)
                dp[2][i][j][k] = min(dp[2][i][j][k], dp[1][i][j][k - 1] + abs(cur - py[k]));
        }
    };

    for (int i = 0; i <= cr; i++) {
        for (int j = 0; j <= cg; j++) {
            for (int k = 0; k <= cy; k++) {
                if (!i && !j && !k) continue;
                for (int last = 0; last < 3; last++)
                    refine(i, j, k, last);
            }
        }
    }
    int opt = min({dp[0][cr][cg][cy], dp[1][cr][cg][cy], dp[2][cr][cg][cy]});
    cout << (opt == INT_MAX ? -1 : opt / 2);

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Incorrect 0 ms 604 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 0 ms 348 KB Output is correct
2 Correct 35 ms 96644 KB Output is correct
3 Correct 34 ms 96604 KB Output is correct
4 Correct 43 ms 96512 KB Output is correct
5 Correct 35 ms 96596 KB Output is correct
6 Correct 35 ms 96596 KB Output is correct
7 Correct 34 ms 96664 KB Output is correct
8 Correct 37 ms 96596 KB Output is correct
9 Correct 36 ms 96084 KB Output is correct
10 Correct 32 ms 96592 KB Output is correct
11 Correct 32 ms 96740 KB Output is correct
12 Correct 9 ms 26968 KB Output is correct
13 Correct 21 ms 47192 KB Output is correct
14 Correct 32 ms 67400 KB Output is correct
15 Correct 37 ms 97112 KB Output is correct
16 Correct 35 ms 97104 KB Output is correct

Subtask #4
0 / 25.0

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