Submission #1063235

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063235		_8_8_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	15 / 100	281 ms	780372 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
    
using namespace std;
    
typedef long long ll;
const int  N = 400 + 12, MOD = (int)1e9 + 7;

int n,dp[N][N][N][3];
vector<int> r,g,y;
void test() {
    cin >> n;
    string s;cin >> s;
    for(int i = 0;i < n;i++) {
        if(s[i] == 'R') {
            r.push_back(i);
        } else if(s[i] == 'Y') {
            y.push_back(i);
        } else {
            g.push_back(i);
        }
    }
    int r_ = (int)r.size(),g_ = (int)g.size(),y_ = (int)y.size();
    for(int i = 0;i <= n;i++) {
        for(int j = 0;j <= n;j++) {
            for(int k = 0;k <= n;k++) {
                for(int t = 0;t < 3;t++) {
                    dp[i][j][k][t] = 1e9;
                }
            }
        }
    }
    for(int i = 0;i < 3;i++) {
        dp[0][0][0][i] = 0;
    }
    for(int i = 0;i <= r_;i++) {
        for(int j = 0;j <= g_;j++) {
            for(int k = 0;k <= y_;k++) {
                for(int t = 0;t < 3;t++){
                    int all = i + j + k;
                    if(i < r_ && t != 0) {
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0],dp[i][j][k][t] + abs(all - r[i]));
                    }
                    if(j < g_ && t != 1) {
                        dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1],dp[i][j][k][t] + abs(all - g[j]));
                    }
                    if(k < y_ && t != 2) {
                        dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2],dp[i][j][k][t] + abs(all - y[k]));
                    }
                }
            }
        }
    }
    int res = 1e9;
    for(int i = 0;i < 3;i++) {
        res = min(res,dp[r_][g_][y_][i]);
    }
    if(res == 1e9) {
        cout << -1;
        return;
    }
    cout << res / 2;
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}  

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