oj.uz

Submission #1086684

# Submission time Handle Problem Language Result Execution time Memory
1086684 2024-09-11T09:06:53 Z _callmelucian Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 75 ms 193920 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][404][404];
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 (last == 2) {
            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 348 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 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 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 1 ms 856 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 348 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 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 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 1 ms 856 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 468 KB Output is correct
2 Correct 59 ms 193720 KB Output is correct
3 Correct 57 ms 192852 KB Output is correct
4 Correct 58 ms 193872 KB Output is correct
5 Correct 57 ms 193876 KB Output is correct
6 Correct 75 ms 193872 KB Output is correct
7 Correct 59 ms 192904 KB Output is correct
8 Correct 63 ms 192852 KB Output is correct
9 Correct 68 ms 191944 KB Output is correct
10 Correct 61 ms 193876 KB Output is correct
11 Correct 64 ms 193872 KB Output is correct
12 Correct 19 ms 52568 KB Output is correct
13 Correct 30 ms 91968 KB Output is correct
14 Correct 44 ms 132688 KB Output is correct
15 Correct 64 ms 193872 KB Output is correct
16 Correct 69 ms 193920 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 0 ms 604 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 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 1 ms 856 KB Output is correct
11 Incorrect 0 ms 604 KB Output isn't correct
12 Halted 0 ms 0 KB -