Submission #1013395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013395		phong	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	100 / 100	355 ms	137556 KiB

joi2019_ho_t3

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 4e5 + 5, N = 4e5;
const ll oo = 1e9;
const int lg = 18, M = 4e3;
const int base = 2e5, mod = 1e9 + 7;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' ';cout << endl
using namespace std;

int n;
int cnt[nmax][3];
void ckmin(int &a, int b){
    a = min(a, b);
}
vector<int> adj[3];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
//    cin >> n;
    string s;
    cin >> n;
    cin >> s;
    s = ' ' + s;
    for(int i = 1; i <= n; ++i){
        int idx;
        if(s[i] == 'R') idx = 0;
        else if(s[i] == 'G') idx = 1;
        else idx = 2;
        adj[idx].push_back(i);
        for(int j = 0; j < 3; ++j) cnt[i][j] = cnt[i - 1][j];
        cnt[i][idx]++;
    }
    for(int j = 0; j < 3; ++j) adj[j].push_back(oo);

    vector<vector<vector<vector<int>>>> dp(cnt[n][0] + 2, vector<vector<vector<int>>> (cnt[n][1] + 2, vector<vector<int>>(cnt[n][2] + 2, vector<int>(3, oo))));
    for(int j = 0; j < 3; ++j) dp[0][0][0][j] = 0;
    for(int c1 = 0; c1 <= cnt[n][0];++c1){
        for(int c2 = 0; c2 <= cnt[n][1];++c2){
            for(int c3 = 0; c3 <= cnt[n][2];++c3){
                int i = c1 + c2 + c3;
                int cur = 0;
                for(int j = 0; j < 3; ++j){
                    if(j == 0) continue;
                    int x = adj[0][c1];

                        int p1 = max(0ll, c2 - (lower_bound(adj[1].begin(), adj[1].end(), x) - adj[1].begin()));
                        int p2 = max(0ll, c3 - (lower_bound(adj[2].begin(), adj[2].end(), x) - adj[2].begin()));
                        int cur = x + p1 + p2 - i - 1;
                        ckmin(dp[c1 + 1][c2][c3][0], dp[c1][c2][c3][j] + cur);
//
                }
                for(int j = 0; j < 3; ++j){
                    if(j == 1) continue;
                    int x = adj[1][c2];

                        int p1 = max(0ll, c1 - (lower_bound(adj[0].begin(), adj[0].end(), x) - adj[0].begin()));
                        int p2 = max(0ll, c3 - (lower_bound(adj[2].begin(), adj[2].end(), x) - adj[2].begin()));
                        int cur = x + p1 + p2 - i - 1;
                        ckmin(dp[c1][c2 + 1][c3][1], dp[c1][c2][c3][j] + cur);

                }
                for(int j = 0; j < 3; ++j){
                    if(j == 2) continue;
                    int x = adj[2][c3];
//                    if(c3 <= cnt[i][2]){
//
//                        cur = x - i - 1;
//                        ckmin(dp[c1][c2][c3 + 1][2], dp[c1][c2][c3][j] + cur);
//                    }
//                    else{
                        int p1 = max(0ll, c1 - (lower_bound(adj[0].begin(), adj[0].end(), x) - adj[0].begin()));
                        int p2 = max(0ll, c2 - (lower_bound(adj[1].begin(), adj[1].end(), x) - adj[1].begin()));
                        int cur = x + p1 + p2 - i - 1;
                        ckmin(dp[c1][c2][c3 + 1][2], dp[c1][c2][c3][j] + cur);
//                    }
                }
            }
        }
    }
//    cout << dp[0][2][3][2]<< ' ';
    int ans = oo;
    for(int i = 0; i < 3; ++i)ans = min(ans, dp[cnt[n][0]][cnt[n][1]][cnt[n][2]][i]);
    if(ans > oo/2) cout << -1;
    else cout << ans;

}
/*
25
RYRRRYGYGGYYGYYRGGYGGGRGG

*/

Compilation message (stderr)

joi2019_ho_t3.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main(){
      | ^~~~
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:50:21: warning: unused variable 'cur' [-Wunused-variable]
   50 |                 int cur = 0;
      |                     ^~~

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