Submission #108751

#	Time	Username	Problem	Language	Result	Execution time	Memory
108751		tictaccat	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	384 ms	192932 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;
const int MAX = 400+2;

int N;
string S;

int dp[3][MAX][MAX][MAX];
int cross[MAX][MAX][MAX];

vector<int> R,G,Y;

int main() {

    cin >> N >> S;

    for (int i = 0; i < N; i++) {
        if (S[i] == 'R') R.push_back(i);
        else if (S[i] == 'G') G.push_back(i);
        else Y.push_back(i);
    }

    for (int r = 0; r <= R.size(); r++) {
        for (int g = 0; g <= G.size(); g++) {
            for (int y = 0; y <= Y.size(); y++) {
                int i = r+g+y;
                for (int c = 0; c < 3; c++) {

                    if (r == 0 && g == 0 && y == 0) {
                        dp[c][r][g][y] = 0;
                        continue;
                    }

                    dp[c][r][g][y] = INF;

                    if (c == 0 && r > 0) {
                        int yInv = y - (upper_bound(Y.begin(),Y.begin()+y,R[r-1]) - Y.begin());
                        int gInv = g - (upper_bound(G.begin(),G.begin()+g,R[r-1]) - G.begin());
                     //   if (r == 2 && g == 0 && y == 1) cout << yInv << " " << gInv << "\n";
                        dp[c][r][g][y] = min(dp[c][r][g][y],min(dp[1][r-1][g][y],dp[2][r-1][g][y]) + gInv + yInv);
                    }
                    if (c == 1 && g > 0) {
                        int yInv = y - (upper_bound(Y.begin(),Y.begin()+y,G[g-1]) - Y.begin());
                        int rInv = r - (upper_bound(R.begin(),R.begin()+r,G[g-1]) - R.begin());
                        dp[c][r][g][y] = min(dp[c][r][g][y],min(dp[0][r][g-1][y],dp[2][r][g-1][y]) + rInv + yInv);

                    }
                    if (c == 2 && y > 0) {
                        int rInv = r - (upper_bound(R.begin(),R.begin()+r,Y[y-1]) - R.begin());
                        int gInv = g - (upper_bound(G.begin(),G.begin()+g,Y[y-1]) - G.begin());
                       // if (r == 2 && g == 0 && y == 1) cout << rInv << " " << gInv << "\n";
                        dp[c][r][g][y] = min(dp[c][r][g][y],min(dp[1][r][g][y-1],dp[0][r][g][y-1]) + gInv + rInv);
                    }

                }
            }
        }
    }

    //cout << dp[0][1][0][1] << "\n";
    int ans = INF;
    for (int c = 0; c < 3; c++) ans = min(ans,dp[c][R.size()][G.size()][Y.size()]);
    
    cout << (ans == INF ? -1 : ans) << "\n";

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:26:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int r = 0; r <= R.size(); r++) {
                     ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:27:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int g = 0; g <= G.size(); g++) {
                         ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:28:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int y = 0; y <= Y.size(); y++) {
                             ~~^~~~~~~~~~~
joi2019_ho_t3.cpp:29:21: warning: unused variable 'i' [-Wunused-variable]
                 int i = r+g+y;
                     ^

• Subtask 1: 5 / 5
• Subtask 2: 55 / 55
• Subtask 3: 15 / 15
• Subtask 4: 25 / 25