oj.uz

Submission #98808

# Submission time Handle Problem Language Result Execution time Memory
98808 2019-02-26T09:08:01 Z bogdan10bos Growing Vegetable is Fun 3 (JOI19_ho_t3) C++14
15 / 100
 372 ms 325572 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;
}
char idtochar(int id)
{
    if(id == 0) return 'R';
    if(id == 1) return 'G';
    if(id == 2) return 'Y';
    return 0;
}

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

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

int eval(string s1, string s2)
{
    /*freopen("1.in", "r", stdin);
    cin >> N;
    string s1, s2;
    cin >> s1 >> s2;*/

    int ans = 0;
    int f[3] = {0}, g[3] = {0};
    for(int i = 0; i < s1.size(); i++)
    {
        int x = getid(s1[i]);
        int y = getid(s2[i]);
        f[x]++;
        g[y]++;

        if(g[y] > f[y])
        {
            for(int j = i + 1; j < s1.size(); j++)
                if(getid(s1[j]) == y)
                {
                    while(j > i)
                    {
                        swap(s1[j], s1[j - 1]);
                        j--;
                        ans++;
                    }
                    break;
                }
        }
        f[x]--;
        f[getid(s1[i])]++;
    }
    return ans;
    //cout << s1 << '\n';
    //cout << s2 << '\n';
    //cout << ans << '\n';

    //exit(0);
}

int main()
{
    //eval();

    #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);
                    lst[r][g][y][0] = (dp[r - 1][g][y][1] > dp[r - 1][g][y][2]) ? 2 : 1;
                }
                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);
                    lst[r][g][y][1] = (dp[r][g - 1][y][0] > dp[r][g - 1][y][2]) ? 2 : 0;
                }
                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);
                    lst[r][g][y][2] = (dp[r][g][y - 1][0] > dp[r][g][y - 1][1]) ? 1 : 0;
                }

                p++;
                p--;
            }

    int ans = min({ dp[R][G][Y][0], dp[R][G][Y][1], dp[R][G][Y][2] });

    int r, g, y, l;
    r = R, g = G, y = Y;
    if(ans == dp[r][g][y][0])   l = 0;
    if(ans == dp[r][g][y][1])   l = 1;
    if(ans == dp[r][g][y][2])   l = 2;

    string mystr;
    while(r + g + y > 0)
    {
        mystr.push_back(idtochar(l));

        int ll = lst[r][g][y][l];
        if(l == 0)  r--;
        if(l == 1)  g--;
        if(l == 2)  y--;
        l = ll;
    }
    reverse(mystr.begin(), mystr.end());

    ans = eval(s, mystr);

    cout << ans << '\n';
    //cout << mystr << '\n';

    return 0;
}

Compilation message

joi2019_ho_t3.cpp: In function 'int eval(std::__cxx11::string, std::__cxx11::string)':
joi2019_ho_t3.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < s1.size(); i++)
                    ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:55:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = i + 1; j < s1.size(); j++)
                                ~~^~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Incorrect 3 ms 640 KB Output isn't correct
6 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 372 ms 325528 KB Output is correct
3 Correct 257 ms 324132 KB Output is correct
4 Correct 245 ms 325572 KB Output is correct
5 Correct 235 ms 325496 KB Output is correct
6 Correct 265 ms 325564 KB Output is correct
7 Correct 238 ms 323880 KB Output is correct
8 Correct 253 ms 323864 KB Output is correct
9 Correct 253 ms 322328 KB Output is correct
10 Correct 267 ms 325528 KB Output is correct
11 Correct 246 ms 325500 KB Output is correct
12 Correct 70 ms 87800 KB Output is correct
13 Correct 124 ms 153976 KB Output is correct
14 Correct 183 ms 222456 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 25.0

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