Submission #512589

#	Time	Username	Problem	Language	Result	Execution time	Memory
512589		Jarif_Rahman	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++17	60 / 100	796 ms	1048580 KiB

joi2019_ho_t3

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
typedef long long int ll;
typedef string str;
const int inf = 1e9+5;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; str ss; cin >> n >> ss;
    vector<int> s;
    for(int i = 0; i < n; i++){
        if(ss[i] == 'R') s.pb(0);
        if(ss[i] == 'G') s.pb(1);
        if(ss[i] == 'Y') s.pb(2);
    }

    vector<vector<int>> cnt(n, vector<int>(3, 0));
    vector<vector<int>> pos(3);
    vector<vector<vector<vector<int>>>> dp(n+1, vector<vector<vector<int>>>(n+1,
        vector<vector<int>>(n+1, vector<int>(3, inf))));

    for(int i = n-1; i >= 0; i--){
        pos[s[i]].pb(i);
        if(i != n-1) cnt[i][0] = cnt[i+1][0], cnt[i][1] = cnt[i+1][1], cnt[i][2] = cnt[i+1][2];
        cnt[i][s[i]]++;
    }

    for(int i = n-1; i >= 0; i--){
        int c[3];
        for(c[0] = 0; c[0] <= min(cnt[0][0], n-i); c[0]++) for(c[1] = 0; c[1] <= cnt[0][1] && c[1]+c[0] <= n-i; c[1]++){
            c[2] = n-i-c[0]-c[1];
            for(int cl = 0; cl < 3; cl++){
                if(c[cl] == 0) continue;
                if(c[cl] > pos[cl].size()) continue;
                vector<int> o;
                for(int j = 0; j < 3; j++) if(j != cl) o.pb(j);
                for(int j = 0; j < 2; j++){
                    int cur = 0;
                    c[cl]--;
                    if(i != n-1) cur+=dp[i+1][c[0]][c[1]][o[j]];
                    c[cl]++;
                    if(i == n-1) cur+=abs(pos[cl][c[cl]-1]-i);
                    else cur+=abs(pos[cl][c[cl]-1]-max(0, c[o[0]]-cnt[pos[cl][c[cl]-1]][o[0]])
                        -max(0, c[o[1]]-cnt[pos[cl][c[cl]-1]][o[1]])-i);

                    dp[i][c[0]][c[1]][cl] = min(dp[i][c[0]][c[1]][cl], cur);
                }
            }
        }
    }
    int ans = inf;
    for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int c = 0; c < 3; c++)
        ans = min(ans, dp[0][i][j][c]);
    if(ans >= inf) ans = -1;
    cout << ans << "\n";
}

Compilation message (stderr)

joi2019_ho_t3.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
joi2019_ho_t3.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
joi2019_ho_t3.cpp: In function 'int main()':
joi2019_ho_t3.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |                 if(c[cl] > pos[cl].size()) continue;
      |                    ~~~~~~^~~~~~~~~~~~~~~~

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