Submission #920268

#	Time	Username	Problem	Language	Result	Execution time	Memory
920268		vjudge1	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	1079 ms	11612 KiB

joi2019_ho_t3

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
const int inf = 1e9,N = 3e5+1;

inline void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (auto& it : s) {
        if (it == 'R') it = 'A';
        else if (it == 'G') it = 'B';
        else it = 'C';
    }
    int dp[n+1][n+1][3][3];
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            for (int k=0;k<3;k++) {
                for (int k2=0;k2<3;k2++) dp[i][j][k][k2] = inf;
            }
        }
    }
    for (int i=1;i<=n;i++) dp[i][i][s[i-1]-'A'][s[i-1]-'A'] = 0;
    for (int L=n;L>=1;L--) {
        for (int R = L+1;R<=n;R++) {
            for (int a = 0;a<3;a++) {
                for (int b=0;b < 3;b++) {
                    for (int x = L;x<R;x++) {
                        for (int i=0;i<3;i++) {
                            for (int j=0;j<3;j++) {
                                if (i == j) continue;
    dp[L][R][a][b]=min(dp[L][R][a][b],dp[L][x][a][i]+dp[x+1][R][j][b]);
    dp[L][R][a][b]=min(dp[L][R][a][b],dp[L][x][i][b]+dp[x+1][R][a][j]+(x-L+1)*(R-x));
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = inf;
    for (int i=0;i<3;i++) for (int j=0;j<3;j++) ans = min(ans,dp[1][n][i][j]);
    cout << ((ans==inf)?-1:ans) << '\n';
}   
    
                 
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
	while (t --> 0) solve();
}

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