Submission #888641

#	Time	Username	Problem	Language	Result	Execution time	Memory
888641		hafo	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	871 ms	781532 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
 
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
 
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 4e2 + 7;
const ll oo = 1e9 + 69;
 
int n;
char a[maxn];
 
struct sub2 {
    int dp[maxn][maxn][maxn][3];
    int cost[maxn][maxn][3], f[maxn][3];
    char b[maxn];
 
    int calc(char ch, int l, int r) {
        for(int i = l; i <= r; i++) b[i] = a[i];
        int ans = 0;
        for(int i = l; i <= r; i++) {
            if(i % 2 == l % 2 && b[i] != ch) {
                bool ok = 0;
                for(int j = i + 1; j <= r; j++) {
                    if(b[j] == ch) {
                        ok = 1;
                        for(int k = j; k > i; k--) {
                            ans++;
                            swap(b[k], b[k - 1]);
                        }
                        break;
                    }
                }
 
                if(!ok) return oo;
            }
 
            if(i % 2 != l % 2 && b[i] == ch) {
                bool ok = 0;
                for(int j = i + 1; j <= r; j++) {
                    if(b[j] != ch) {
                        ok = 1;
                        for(int k = j; k > i; k--) {
                            ans++;
                            swap(b[k], b[k - 1]);
                        }
                        break;
                    }
                }
                if(!ok) return oo;
            }
        }
        return ans;
    }
 
    void compute(int l, int r) {
        vector<char> ch;
        for(int i = l; i <= r; i++) ch.pb(a[i]);
        sort(all(ch));
        ch.erase(unique(all(ch)), ch.end());
 
        if(Size(ch) == 3) return;
 
        int ans = oo;
        int t;
        if(l % 2 == r % 2) t = convert(ch.front());
        else t = convert(ch.back());
        cost[l][r][t] = calc(ch.front(), l, r);
 
        if(l % 2 == r % 2) t = convert(ch.back());
        else t = convert(ch.front());
        cost[l][r][t] = calc(ch.back(), l, r);
    }
 
    int convert(char ch) {
        if(ch == 'R') return 0;
        if(ch == 'G') return 1;
        return 2;
    }
 
    void solve() {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                for(int cur = 0; cur < 3; cur++) cost[i][j][cur] = oo;
            }
        }
        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                compute(i, j);
            }
        }
 
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 3; j++) f[i][j] = f[i - 1][j];
            f[i][convert(a[i])]++;
        }
 
        for(int i = 0; i <= n; i++) {
            for(int red = 0; red <= f[n][0]; red++) {
                for(int green = 0; green <= f[n][1]; green++) {
                    for(int cur = 0; cur < 3; cur++) dp[i][red][green][cur] = oo;
                }
            }
        }
 
        dp[0][0][0][0] = 0;
        dp[0][0][0][1] = 0;
        dp[0][0][0][2] = 0;
 
        for(int i = 0; i < n; i++) {
            for(int red = 0; red <= f[n][0]; red++) {
                for(int green = 0; green <= f[n][1]; green++) {
                    for(int cur = 0; cur < 3; cur++) {
                        if(dp[i][red][green][cur] == oo) continue;
 
                        int yellow = i - red - green;
                        if(yellow < 0) continue;
 
                        // swap time
                        if(i != 0) {
                            for(int nxt = 0; nxt < 3; nxt++) {
                                if(nxt == cur) continue;
                                for(int j = i + 1; j <= n; j++) {

                                    if(convert(a[j]) == nxt) {
                                        int new_red = red + f[j][0] - f[i][0];
                                        int new_green = green + f[j][1] - f[i][1];
                                        int new_yellow = yellow + f[j][2] - f[i][2];
                                        if(new_red <= f[n][0] && new_green <= f[n][1] && new_yellow <= f[n][2]) {
                                            for(int nxt2 = 0; nxt2 < 3; nxt2++) {
                                                if(nxt == nxt2 || f[j][nxt2] - f[i][nxt2] == 0) continue;
                                                mini(dp[j][new_red][new_green][nxt2], dp[i][red][green][cur] + (i + 1 <= j - 1 ? cost[i + 1][j - 1][nxt2]:0) + j - i);
                                                if(j == 3 && new_red == 2 && new_green == 1 && nxt2 == 1) cout<<i<<" "<<cur<<" "<<nxt<<"\n";
                                            }
                                        }
                                        break;
                                    }
                                }
                            }
                        }
 
                        for(int j = i + 1; j <= n; j++) {
                            vector<int> ch;
                            if(f[j][0] - f[i][0] > 0) ch.pb(0);
                            if(f[j][1] - f[i][1] > 0) ch.pb(1);
                            if(f[j][2] - f[i][2] > 0) ch.pb(2);
                            if(Size(ch) == 3) break;

                            for(auto nxt:ch) {
                                int t, l = i + 1, r = j;
                                if(l % 2 == r % 2) t = nxt;
                                else {
                                    if(nxt == ch.front()) t = ch.back();
                                    else t = ch.front();
                                }

                                if(cur == t) continue;

                                int new_red = red + f[j][0] - f[i][0];
                                int new_green = green + f[j][1] - f[i][1];
                                int new_yellow = yellow + f[j][2] - f[i][2];
                                if(new_red <= f[n][0] && new_green <= f[n][1] && new_yellow <= f[n][2]) {
                                    mini(dp[j][new_red][new_green][nxt], dp[i][red][green][cur] + cost[i + 1][j][nxt]);
                                }
                            }
                        }
                    }
                }
            }
        }
        
        int ans = oo;   
        for(int i = 0; i < 3; i++) mini(ans, dp[n][f[n][0]][f[n][1]][i]);
        cout<<(ans == oo ? -1:ans);
    }
 
} sub2;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);
 
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
 
    sub2.solve();
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In member function 'void sub2::compute(int, int)':
joi2019_ho_t3.cpp:76:13: warning: unused variable 'ans' [-Wunused-variable]
   76 |         int ans = oo;
      |             ^~~

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