Submission #771375

#	Time	Username	Problem	Language	Result	Execution time	Memory
771375		raysh07	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	0 / 100	1083 ms	17980 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    string s; cin >> s;
    s = "0" + s;
    
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(3, INF)));
    dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 0;
    vector <int> cnt(3, 0);
    
    for (int i = 1; i <= n; i++){
        vector<vector<vector<int>>> ndp(n + 1, vector<vector<int>>(n + 1, vector<int>(3, INF)));
        if (s[i] == 'R') cnt[0]++;
        else if (s[i] == 'G') cnt[1]++;
        else cnt[2]++;
        
        vector <int> j(3, 0);
        
        for (j[0] = 0; j[0] <= i; j[0]++){
            for (j[1] = 0; j[1] <= i; j[1]++){
                j[2] = i - j[0] - j[1];
                if (j[2] < 0) continue;
                
                int cost = 0;
                for (int k = 0; k < 3; k++){
                    cost += max(0LL, cnt[k] - j[k]);
                }
                
                int mi = INF;
                if (j[0] != 0) ndp[j[0]][j[1]][0] = cost + min(dp[j[0] - 1][j[1]][1], dp[j[0] - 1][j[1]][2]);
                if (j[1] != 0) ndp[j[0]][j[1]][1] = cost + min(dp[j[0]][j[1] - 1][0], dp[j[0]][j[1] - 1][2]);
                if (j[2] != 0) ndp[j[0]][j[1]][2] = cost + min(dp[j[0]][j[1]][0], dp[j[0]][j[1]][1]);
            }
        }
        
        dp = ndp;
    }
    
    int ans = INF;
    for (int i = 0; i < 3; i++) ans = min(ans, dp[cnt[0]][cnt[1]][i]);
    if (ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
   // cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

Compilation message (stderr)

joi2019_ho_t3.cpp: In function 'void Solve()':
joi2019_ho_t3.cpp:38:21: warning: unused variable 'mi' [-Wunused-variable]
   38 |                 int mi = INF;
      |                     ^~

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