Submission #98808

#	Time	Username	Problem	Language	Result	Execution time	Memory
98808		bogdan10bos	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	15 / 100	372 ms	325572 KiB

joi2019_ho_t3

#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 (stderr)

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
• Subtask 2: 0 / 55
• Subtask 3: 15 / 15
• Subtask 4: 0 / 25