Submission #1127253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127253		Zero_OP	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++20	100 / 100	96 ms	162888 KiB

joi2019_ho_t3

#include <bits/stdc++.h>

using namespace std;

const int MAX = 402;
const int inf = 1e9;

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
bool minimize(T& a, const T& b){
    if(a > b) return a = b, true;
    return false;
}

int N, n[3], pos[3][MAX], cnt[3][MAX], cl[MAX], up[3][MAX], ind[MAX];
int dp[MAX][MAX][MAX][3];

int main(){
//    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N;
    for(int i = 1; i <= N; ++i){
        char c; cin >> c;
        int t = (c == 'R' ? 0 : (c == 'G' ? 1 : 2));
        pos[t][++n[t]] = i;
        ind[i] = n[t];
        cl[i] = t;

        for(int j = 0; j < 3; ++j) cnt[j][i] = cnt[j][i - 1];
        ++cnt[t][i];
    }

    up[0][N + 1] = N + 1;
    up[1][N + 1] = N + 1;
    up[2][N + 1] = N + 1;

    for(int i = N; i >= 1; --i){
        for(int j = 0; j < 3; ++j) up[j][i] = up[j][i + 1];
        up[cl[i]][i] = i;
    }

    for(int i = 0; i <= n[0]; ++i){
        for(int j = 0; j <= n[1]; ++j){
            for(int k = 0; k <= n[2]; ++k){
                for(int l = 0; l <= 3; ++l){
                    dp[i][j][k][l] = inf;
                }
            }
        }
    }

    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][0][0][2] = 0;

    for(int i = 0; i <= n[0]; ++i){
        for(int j = 0; j <= n[1]; ++j){
            for(int k = 0; k <= n[2]; ++k){
                int s = i + j + k;
                for(int l = 0; l <= 2; ++l){
                    if(dp[i][j][k][l] == inf) continue;

//                    cout << "[" << i << ", " << j << ", " << k << ", " << l << "] : ";

                    if(l != 0 && i < n[0]){
                        int nxt = pos[0][i + 1];
                        int v1 = up[1][nxt];
                        int v2 = up[2][nxt];
                        int result = 0;
                        if(v1 != N + 1 && ind[v1] <= j){
                            result += j - ind[v1] + 1;
                        }

                        if(v2 != N + 1 && ind[v2] <= k){
                            result += k - ind[v2] + 1;
                        }

                        minimize(dp[i + 1][j][k][0], dp[i][j][k][l] + (nxt + result) - (s + 1));
                    }

                    if(l != 1 && j < n[1]){
                        int nxt = pos[1][j + 1];
                        int v0 = up[0][nxt];
                        int v2 = up[2][nxt];
                        int result = 0;
                        if(v0 != N + 1 && ind[v0] <= i){
                            result += i - ind[v0] + 1;
                        }

                        if(v2 != N + 1 && ind[v2] <= k){
                            result += k - ind[v2] + 1;
                        }

                        minimize(dp[i][j + 1][k][1], dp[i][j][k][l] + (nxt + result) - (s + 1));
                    }

                    if(l != 2 && k < n[2]){
                        int nxt = pos[2][k + 1];
                        int v0 = up[0][nxt];
                        int v1 = up[1][nxt];
                        int result = 0;
                        if(v0 != N + 1 && ind[v0] <= i){
                            result += i - ind[v0] + 1;
                        }

                        if(v1 != N + 1 && ind[v1] <= j){
                            result += j - ind[v1] + 1;
                        }

                        minimize(dp[i][j][k + 1][2], dp[i][j][k][l] + (nxt + result) - (s + 1));
                    }

//                    cout << '\n';
                }
            }
        }
    }

    int ans = inf;
    for(int i = 0; i <= 3; ++i){
        minimize(ans, dp[n[0]][n[1]][n[2]][i]);
    }

    if(ans == inf) ans = -1;
    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:12:10: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
   12 |     if(a > b) return a = b, true;
      |        ~~^~~
joi2019_ho_t3.cpp:126:22: note: within this loop
  126 |     for(int i = 0; i <= 3; ++i){
      |                    ~~^~~~
joi2019_ho_t3.cpp:52:36: warning: iteration 3 invokes undefined behavior [-Waggressive-loop-optimizations]
   52 |                     dp[i][j][k][l] = inf;
      |                     ~~~~~~~~~~~~~~~^~~~~
joi2019_ho_t3.cpp:51:34: note: within this loop
   51 |                 for(int l = 0; l <= 3; ++l){
      |                                ~~^~~~

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