oj.uz

답안 #367024

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
367024 2021-02-16T04:22:26 Z Lam_lai_cuoc_doi Growing Vegetable is Fun 3 (JOI19_ho_t3) C++17
0 / 100
 500 ms 781932 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;
        }
    }
    fill_n(&dp[0][0][0][0], N * N * N * 3, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 780432 KB Output is correct
2 Correct 477 ms 780368 KB Output is correct
3 Correct 477 ms 780396 KB Output is correct
4 Correct 478 ms 780396 KB Output is correct
5 Correct 480 ms 780396 KB Output is correct
6 Correct 477 ms 780524 KB Output is correct
7 Correct 477 ms 780524 KB Output is correct
8 Correct 483 ms 780396 KB Output is correct
9 Correct 479 ms 780412 KB Output is correct
10 Correct 476 ms 780524 KB Output is correct
11 Correct 483 ms 780524 KB Output is correct
12 Correct 477 ms 780652 KB Output is correct
13 Incorrect 478 ms 780404 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 780432 KB Output is correct
2 Correct 477 ms 780368 KB Output is correct
3 Correct 477 ms 780396 KB Output is correct
4 Correct 478 ms 780396 KB Output is correct
5 Correct 480 ms 780396 KB Output is correct
6 Correct 477 ms 780524 KB Output is correct
7 Correct 477 ms 780524 KB Output is correct
8 Correct 483 ms 780396 KB Output is correct
9 Correct 479 ms 780412 KB Output is correct
10 Correct 476 ms 780524 KB Output is correct
11 Correct 483 ms 780524 KB Output is correct
12 Correct 477 ms 780652 KB Output is correct
13 Incorrect 478 ms 780404 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 487 ms 780320 KB Output is correct
2 Correct 500 ms 781700 KB Output is correct
3 Correct 490 ms 781580 KB Output is correct
4 Correct 479 ms 781676 KB Output is correct
5 Correct 487 ms 781932 KB Output is correct
6 Correct 479 ms 781676 KB Output is correct
7 Correct 485 ms 781676 KB Output is correct
8 Correct 486 ms 781736 KB Output is correct
9 Correct 486 ms 781676 KB Output is correct
10 Correct 497 ms 781676 KB Output is correct
11 Execution timed out 504 ms 781676 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 500 ms 780432 KB Output is correct
2 Correct 477 ms 780368 KB Output is correct
3 Correct 477 ms 780396 KB Output is correct
4 Correct 478 ms 780396 KB Output is correct
5 Correct 480 ms 780396 KB Output is correct
6 Correct 477 ms 780524 KB Output is correct
7 Correct 477 ms 780524 KB Output is correct
8 Correct 483 ms 780396 KB Output is correct
9 Correct 479 ms 780412 KB Output is correct
10 Correct 476 ms 780524 KB Output is correct
11 Correct 483 ms 780524 KB Output is correct
12 Correct 477 ms 780652 KB Output is correct
13 Incorrect 478 ms 780404 KB Output isn't correct
14 Halted 0 ms 0 KB -