Submission #1063257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063257		_8_8_	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	299 ms	781652 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],pr[N],pg[N],py[N];
vector<int> r,g,y;
void test() {
    cin >> n;
    string s;cin >> s;
    for(int i = 0;i < n;i++) {
        if(i) {
            pr[i] = pr[i - 1];
            pg[i] = pg[i  - 1];
            py[i] = py[i - 1];
        }
        if(s[i] == 'R') {
            pr[i]++;
            r.push_back(i);
        } else if(s[i] == 'Y') {
            y.push_back(i);
            py[i]++;
        } else {
            g.push_back(i);
            pg[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;
                    auto get = [&](int ind) -> int{
                        int ret =0 ;
                        ret += max(0,pr[ind] - i);
                        ret += max(0,pg[ind] - k);
                        ret += max(0,py[ind] - j);
                        return ret;
                    };
                    int ind;
                    if(i < r_ && t != 0) {
                        ind = r[i];
                        int val = max(0,pg[ind] - j) + max(0,py[ind] - k);
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0],dp[i][j][k][t] + val);
                    }
                    if(j < g_ && t != 1) {
                        ind = g[j];
                        int val = max(0,pr[ind] - i) + max(0,py[ind] - k);
                        dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1],dp[i][j][k][t] + val);
                    }
                    if(k < y_ && t != 2) {
                        ind = y[k];
                        int val = max(0,pr[ind] - i) + max(0,pg[ind] - j);
                        dp[i][j][k + 1][2] = min(dp[i][j][k + 1][2],dp[i][j][k][t] +val);
                    }
                }
            }
        }
    }
    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 ;
}
int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}  

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void test()':
joi2019_ho_t3.cpp:47:25: warning: unused variable 'all' [-Wunused-variable]
   47 |                     int all = i + j + k;
      |                         ^~~
joi2019_ho_t3.cpp:48:26: warning: variable 'get' set but not used [-Wunused-but-set-variable]
   48 |                     auto get = [&](int ind) -> int{
      |                          ^~~

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