Submission #209274

#	Time	Username	Problem	Language	Result	Execution time	Memory
209274		AryaKnight	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	100 / 100	493 ms	263008 KiB

joi2019_ho_t3

    #pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline") //Optimization flags
    #pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
    #pragma GCC target("avx2")  //Enable AVX
    #include<bits/stdc++.h>
    using namespace std;
     
    #define all(a) begin(a),end(a)
    #define F first
    #define S second
    #define pb push_back
    #define mp make_pair
    typedef long long ll;
    typedef vector<int> vi;
    typedef pair<int,int> pi;
     
    #ifdef LOCAL
    #include "debug.h"
    #else
    #define debug(...) 42
    #endif
     
    void clr(auto &a,int n){
      a.clear();
      a.resize(n);
    }
     
    template <typename A, typename B>
    istream& operator>>(istream& input,pair<A,B>& x) {
      input>>x.F>>x.S;
      return input;
    }
     
    template <typename A>
    istream& operator>>(istream& input,vector<A>& x) {
      for(auto& i:x)
        input>>i;
      return input;
    }
     
    template<typename A>
    ostream& operator<<(ostream& output,vector<A>& x) {
      for(auto& i:x)
        output<<i<<' ';
      return output;
    }
     
    template<typename T>
    vector<pair<T,int>> getvec(int n){
      vector<pair<T,int>>a(n);
      for(int i=0;i<a.size();i++){
        cin>>a[i].F;
        a[i].S=i;
      }
      return a;
    }
     
    const int mod=1e9+7;
     
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
     
    int mul(int a,int b){
      return ((a)*1ll*(b))%mod;
    }
     
    void add(int &a,int b){
      a+=b;
      if(a>=mod)a-=mod;
    }
     
    int sub(int a,int b){
      a-=b;
      if(a<0){
        a+=mod;
      }
      return a;
    }
     
    int powz(int a,int b){
      int res=1;
      while(b){
        if(b&1){
          res=mul(res,a);
        }
        b/=2;
        a=mul(a,a);
      }
      return res;
    }
     
    const int N=405;
     
    int dp[405][405][3],new_dp[405][405][3];
    vector<int>adj[3];
    struct ordered_set {
      int sz = 0, bit[N];
     
      int size() {
        return sz;
      }
     
      void update(int k, int x) {
        k++;
        while (k < N) {
          bit[k] += x;
          k += k & -k;
        }
        sz += x;
      }
     
      int find_by_order(int k) {
        int ans = 0, sum = 0;
        for (int j = 17; j >= 0; --j) {
          ans += 1 << j;
          if (ans < N && sum + bit[ans] < k) {
            sum += bit[ans];
          } else {
            ans -= 1 << j;
          }
        }
        return ans + 1;
      }
     
      int order_of_key(int k) {
        k++;
        int ans = 0;
        while (k >= 1) {
          ans += bit[k];
          k -= k & -k;
        }
        return ans - 1;
      }
    }st[405][405];
     
    vector<int>rv;
     
    void solve(){
      int n;
      cin>>n;
      string s;
      cin>>s;
      rv.resize(n);
      for(int i=0;i<s.length();i++){
        if(s[i]=='R'){
          adj[0].pb(i);
          rv[i]=adj[0].size()-1;
        }
        else if(s[i]=='G'){
          adj[1].pb(i);
          rv[i]=adj[1].size()-1;
        }
        else{
          adj[2].pb(i);
        }
      }
      int mx=max({(int)adj[0].size(),(int)adj[1].size(),(int)adj[2].size()});
      if(mx*2>(n+10)){
        cout<<-1;
        return;
      }
      for(int i=0;i<=adj[0].size();i++){
        for(int j=0;j<=adj[1].size();j++){
          for(int k=0;k<n;k++){
            if(s[k]=='R'){
              if(rv[k]>=i){
                st[i][j].update(k,1);
              }
            }
            else if(s[k]=='G'){
              if(rv[k]>=j){
                st[i][j].update(k,1);
              }
            }
            else{
              st[i][j].update(k,1);
            }
          }
        }
      }
      for(int j=0;j<=adj[0].size();j++){
        for(int k=0;k<=adj[1].size();k++){
          for(int l=0;l<3;l++){
            dp[j][k][l]=new_dp[j][k][l]=1e9;
          }
        }
      }
      dp[0][0][0]=0;
      dp[0][0][1]=0;
      dp[0][0][2]=0;
      for(int i=0;i<n;i++){
        for(int j=0;j<=min(i,(int)adj[0].size());j++){
          for(int k=0;k<=min(i,(int)adj[1].size());k++){
            if(i-(j+k)<0){
              break;
            }
            //for(int l=0;l<3;l++){
	    int l=0;
              if(dp[j][k][l]!=1e9){
                
               int put=0;
                if(put!=l){
                  if(j+1<=adj[0].size()){
                    
                  
	       
                  int fnd=st[j][k].order_of_key(adj[0][j]);
                  new_dp[j+1][k][0]=min(new_dp[j+1][k][0],dp[j][k][l]+fnd);}
                }
              put=1;
                if(put!=l){
                  if(k+1<=adj[1].size()){
                    
                  int fnd=st[j][k].order_of_key(adj[1][k]);
                  new_dp[j][k+1][1]=min(new_dp[j][k+1][1],dp[j][k][l]+fnd);}
                }
              put=2;
                if(put!=l){
                  if((i-(j+k)+1)<=adj[2].size()){
                   
                  int fnd=st[j][k].order_of_key(adj[2][i-(j+k)]);
                  new_dp[j][k][2]=min(new_dp[j][k][2],dp[j][k][l]+fnd);}
              }
	      }
	      l=1;
	      if(dp[j][k][l]!=1e9){
                
               int put=0;
                if(put!=l){
                  if(j+1<=adj[0].size()){
                    
                  
	       
                  int fnd=st[j][k].order_of_key(adj[0][j]);
                  new_dp[j+1][k][0]=min(new_dp[j+1][k][0],dp[j][k][l]+fnd);}
                }
              put=1;
                if(put!=l){
                  if(k+1<=adj[1].size()){
                    
                  int fnd=st[j][k].order_of_key(adj[1][k]);
                  new_dp[j][k+1][1]=min(new_dp[j][k+1][1],dp[j][k][l]+fnd);}
                }
              put=2;
                if(put!=l){
                  if((i-(j+k)+1)<=adj[2].size()){
                   
                  int fnd=st[j][k].order_of_key(adj[2][i-(j+k)]);
                  new_dp[j][k][2]=min(new_dp[j][k][2],dp[j][k][l]+fnd);}
              }
	      }
	      l=2;
	      if(dp[j][k][l]!=1e9){
                
               int put=0;
                if(put!=l){
                  if(j+1<=adj[0].size()){
                    
                  
	       
                  int fnd=st[j][k].order_of_key(adj[0][j]);
                  new_dp[j+1][k][0]=min(new_dp[j+1][k][0],dp[j][k][l]+fnd);}
                }
              put=1;
                if(put!=l){
                  if(k+1<=adj[1].size()){
                    
                  int fnd=st[j][k].order_of_key(adj[1][k]);
                  new_dp[j][k+1][1]=min(new_dp[j][k+1][1],dp[j][k][l]+fnd);}
                }
              put=2;
                if(put!=l){
                  if((i-(j+k)+1)<=adj[2].size()){
                   
                  int fnd=st[j][k].order_of_key(adj[2][i-(j+k)]);
                  new_dp[j][k][2]=min(new_dp[j][k][2],dp[j][k][l]+fnd);}
              }
	      }
            }
        }
        for(int j=0;j<=min(i+1,(int)adj[0].size());j++){
          for(int k=0;k<=min(i+1,(int)adj[1].size());k++){
            if(i-(j+k)<0){
              break;
            }
            if(i+1-(j+k)>adj[2].size()){
              continue;
            }
            st[j][k].update(adj[2][i-(j+k)],-1);
          }
        }
        for(int j=0;j<=(int)adj[0].size();j++){
          for(int k=0;k<=(int)adj[1].size();k++){
            for(int l=0;l<3;l++){
              dp[j][k][l]=new_dp[j][k][l];
              new_dp[j][k][l]=1e9;
            }
          }
        }
      }
      int ans=1e9;
      ans=min(ans,dp[adj[0].size()][adj[1].size()][0]);
      ans=min(ans,dp[adj[0].size()][adj[1].size()][1]);
      ans=min(ans,dp[adj[0].size()][adj[1].size()][2]);
      if(ans==1e9){
        ans=-1;
      }
      cout<<ans;  
    }
     
    signed main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
      int tc=1;
      //cin>>tc;
      for(int _=0;_<tc;_++){
        // cout<<"Case #"<<_+1<<": ";
        solve();
        if(_!=tc-1){
          cout<<'\n';
        }
      }
    }

Compilation message (stderr)

joi2019_ho_t3.cpp:2:0: warning: ignoring #pragma GCC option [-Wunknown-pragmas]
     #pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX
 
joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:142:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<s.length();i++){
                   ~^~~~~~~~~~~
joi2019_ho_t3.cpp:160:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<=adj[0].size();i++){
                   ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:161:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<=adj[1].size();j++){
                     ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:179:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int j=0;j<=adj[0].size();j++){
                   ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:180:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int k=0;k<=adj[1].size();k++){
                     ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:201:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(j+1<=adj[0].size()){
                      ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:210:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(k+1<=adj[1].size()){
                      ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:217:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if((i-(j+k)+1)<=adj[2].size()){
                      ~~~~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:228:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(j+1<=adj[0].size()){
                      ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:237:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(k+1<=adj[1].size()){
                      ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:244:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if((i-(j+k)+1)<=adj[2].size()){
                      ~~~~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:255:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(j+1<=adj[0].size()){
                      ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:264:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if(k+1<=adj[1].size()){
                      ~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:271:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   if((i-(j+k)+1)<=adj[2].size()){
                      ~~~~~~~~~~~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:284:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(i+1-(j+k)>adj[2].size()){
                ~~~~~~~~~^~~~~~~~~~~~~~

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