oj.uz

Submission #98803

# Submission time Handle Problem Language Result Execution time Memory
98803 2019-02-26T08:18:05 Z bogdan10bos Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 139 ms 163064 KB 
#include <bits/stdc++.h>

using namespace std;

//#define FILE_IO

typedef pair<int, int> pii;

int N;
string s;

int getid(char ch)
{
    if(ch == 'R')   return 0;
    if(ch == 'G')   return 1;
    if(ch == 'Y')   return 2;
    return -1;
}

int dp[405][405][405][3];  /// dp[r][g][y]
vector<int> pos[3];

int cost(int x, int y)
{
    if(x < y)   return 0;
    return (x - y);
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    #endif

    cin >> N;
    cin >> s;

    for(int i = 0; i < N; i++)
        pos[getid(s[i])].push_back(i + 1);

    int R = pos[0].size(), G = pos[1].size(), Y = pos[2].size();

    int mx = max({R, G, Y});
    if(mx > (N + 1) / 2)
    {
        printf("-1\n");
        exit(0);
    }

    for(int r = 0; r <= R; r++)
        for(int g = 0; g <= G; g++)
            for(int y = 0; y <= Y; y++)
            {
                int p = r + g + y;
                if(p == 0)  continue;

                dp[r][g][y][0] = dp[r][g][y][1] = dp[r][g][y][2] = 1 << 30;
                if(r > 0)   dp[r][g][y][0] = min(dp[r - 1][g][y][1], dp[r - 1][g][y][2]) + cost(pos[0][r - 1], p);
                if(g > 0)   dp[r][g][y][1] = min(dp[r][g - 1][y][0], dp[r][g - 1][y][2]) + cost(pos[1][g - 1], p);
                if(y > 0)   dp[r][g][y][2] = min(dp[r][g][y - 1][0], dp[r][g][y - 1][1]) + cost(pos[2][y - 1], p);
            }

    int ans = min({ dp[R][G][Y][0], dp[R][G][Y][1], dp[R][G][Y][2] });
    cout << ans << '\n';

    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Incorrect 2 ms 512 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 3 ms 428 KB Output is correct
2 Correct 126 ms 162988 KB Output is correct
3 Correct 129 ms 162208 KB Output is correct
4 Correct 128 ms 162920 KB Output is correct
5 Correct 129 ms 163064 KB Output is correct
6 Correct 139 ms 162936 KB Output is correct
7 Correct 133 ms 162140 KB Output is correct
8 Correct 122 ms 162296 KB Output is correct
9 Correct 117 ms 161404 KB Output is correct
10 Correct 132 ms 163064 KB Output is correct
11 Correct 122 ms 163064 KB Output is correct
12 Correct 34 ms 44032 KB Output is correct
13 Correct 59 ms 77176 KB Output is correct
14 Correct 84 ms 111480 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 25.0

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