Submission #1123428

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123428		LucaIlie	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	360 ms	523360 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 400;
const int R = 0;
const int G = 1;
const int Y = 2;
const int INF = 1e6;
vector<int> pos[3];
int cnt[3][3][MAX_N][MAX_N];
int dp[MAX_N][MAX_N][MAX_N][3];

int main() {
    int n;
    string s;

    cin >> n >> s;
    for ( int c = 0; c < 3; c++ )
        pos[c].push_back( -1 );
    for ( int i = 0; i < n; i++ ) {
        if ( s[i] == 'R' )
            pos[R].push_back( i );
        else if ( s[i] == 'G' )
            pos[G].push_back( i );
        else
            pos[Y].push_back( i );
    }

    for ( int c = 0; c < 3; c++ ) {
        for ( int d = 0; d < 3; d++ ) {
            for ( int i = 1; i < pos[c].size(); i++ ) {
                for ( int j = 1; j < pos[d].size(); j++ ) {
                    cnt[c][d][i][j] = cnt[c][d][i][j - 1];
                    if ( pos[d][j] > pos[c][i] )
                        cnt[c][d][i][j]++;
                }
            }
        }
    }
    for ( int i = 0; i < n; i++ ) {
        for ( int r = 0; r < pos[R].size(); r++ ) {
            for ( int g = 0; g < pos[G].size(); g++ ) {
                for ( int c = 0; c <= 3; c++ )
                    dp[i][r][g][c] = INF;
            }
        }
    }
    if ( pos[R].size() > 1 )
        dp[0][1][0][R] = pos[R][1];
    if ( pos[G].size() > 1 )
        dp[0][0][1][G] = pos[G][1];
    if ( pos[Y].size() > 1 )
        dp[0][0][0][Y] = pos[Y][1];
    for ( int i = 0; i < n; i++ ) {
        for ( int r = 0; r < pos[R].size() && r <= i + 1; r++ ) {
            for ( int g = 0; g < pos[G].size() && g + r <= i + 1; g++ ) {
                int y = i + 1 - r - g;
                for ( int c = 0; c < 3; c++ ) {
                    if ( dp[i][r][g][c] == INF )
                        continue;

                    if ( c != R && r + 1 < pos[R].size() ) {
                        int add = pos[R][r + 1] - (i + 1) + cnt[R][G][r + 1][g] + cnt[R][Y][r + 1][y];
                        dp[i + 1][r + 1][g][R] = min( dp[i + 1][r + 1][g][R], dp[i][r][g][c] + add );
                    }

                    if ( c != G && g + 1 < pos[G].size() ) {
                        int add = pos[G][g + 1] - (i + 1) + cnt[G][R][g + 1][r] + cnt[G][Y][g + 1][y];
                        dp[i + 1][r][g + 1][G] = min( dp[i + 1][r][g + 1][G], dp[i][r][g][c] + add );
                    }

                    if ( c != Y && y + 1 < pos[Y].size() ) {
                        int add = pos[Y][y + 1] - (i + 1) + cnt[Y][G][y + 1][g] + cnt[Y][R][y + 1][r];
                        dp[i + 1][r][g][Y] = min( dp[i + 1][r][g][Y], dp[i][r][g][c] + add );
                    }
                }
            }
        }
    }

    int ans = min( min( dp[n - 1][pos[R].size() - 1][pos[G].size() - 1][R], dp[n - 1][pos[R].size() - 1][pos[G].size() - 1][G] ), dp[n - 1][pos[R].size() - 1][pos[G].size() - 1][Y] );
    cout << (ans == INF ? -1 : ans) << "\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:45:36: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
   45 |                     dp[i][r][g][c] = INF;
      |                     ~~~~~~~~~~~~~~~^~~~~
joi2019_ho_t3.cpp:44:36: note: within this loop
   44 |                 for ( int c = 0; c <= 3; c++ )
      |                                  ~~^~~~

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