제출 #209250

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
209250		AryaKnight	Growing Vegetable is Fun 3 (JOI19_ho_t3)	C++14	0 / 100	130 ms	260984 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[2][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];

void solve(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  for(int i=0;i<s.length();i++){
    if(s[i]=='R'){
      adj[0].pb(i);
    }
    else if(s[i]=='G'){
      adj[1].pb(i);
    }
    else{
      adj[2].pb(i);
    }
  }
  int mx=max({(int)adj[0].size(),(int)adj[1].size(),(int)adj[2].size()});
  if(mx*2>n){
    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++){
	st[i][j].update(k,1);
      }
      for(int k=0;k<i;k++){
	st[i][j].update(adj[0][k],-1);
      }
      for(int k=0;k<j;k++){
	st[i][j].update(adj[1][k],-1);
      }
    }
  }
  for(int i=0;i<2;i++){
    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[i][j][k][l]=1e9;
	}
      }
    }
  }
  dp[0][0][0][0]=0;
  dp[0][0][0][1]=0;
  dp[0][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){
	  continue;
	}
	for(int l=0;l<3;l++){
	  if(dp[0][j][k][l]==1e9){
	    continue;
	  }
	  for(int put=0;put<3;put++){
	    if(put==l){
	      continue;
	    }
	    if(put==0){
	      if(j+1>adj[0].size()){
		continue;
	      }
	      int fnd=st[j][k].order_of_key(adj[0][j]);
	      dp[1][j+1][k][0]=min(dp[1][j+1][k][0],dp[0][j][k][l]+fnd);
	    }
	    else if(put==1){
	      if(k+1>adj[1].size()){
		continue;
	      }
	      int fnd=st[j][k].order_of_key(adj[1][k]);
	      dp[1][j][k+1][1]=min(dp[1][j][k+1][1],dp[0][j][k][l]+fnd);
	    }
	    else{
	      if((i-(j+k)+1)>adj[2].size()){
		continue;
	      }
	      int fnd=st[j][k].order_of_key(adj[2][i-(j+k)]);
	      dp[1][j][k][2]=min(dp[1][j][k][2],dp[0][j][k][l]+fnd);
	    }
	  }
	}
      }
    }
    for(int j=0;j<=adj[0].size();j++){
      for(int k=0;k<=adj[1].size();k++){
	if(i-(j+k)<0){
	  continue;
	}
	if(i+1-(j+k)>adj[2].size()){
	  continue;
	}
	st[j][k].update(adj[2][i-(j+k)],-1);
      }
    }
    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++){
	for(int l=0;l<3;l++){
	  dp[0][j][k][l]=dp[1][j][k][l];
	  dp[1][j][k][l]=1e9;
	}
      }
    }
  }
  int ans=1e9;
  ans=min(ans,dp[0][adj[0].size()][adj[1].size()][0]);
  ans=min(ans,dp[0][adj[0].size()][adj[1].size()][1]);
  ans=min(ans,dp[0][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';
    }
  }
}

컴파일 시 표준 에러 (stderr) 메시지

joi2019_ho_t3.cpp: In function 'void solve()':
joi2019_ho_t3.cpp:139:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<s.length();i++){
               ~^~~~~~~~~~~
joi2019_ho_t3.cpp:155:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<=adj[0].size();i++){
               ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:156:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<=adj[1].size();j++){
                 ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:169:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<=adj[0].size();j++){
                 ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:170:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int k=0;k<=adj[1].size();k++){
                   ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:195:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if(j+1>adj[0].size()){
           ~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:202:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if(k+1>adj[1].size()){
           ~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:209:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        if((i-(j+k)+1)>adj[2].size()){
           ~~~~~~~~~~~^~~~~~~~~~~~~~
joi2019_ho_t3.cpp:219:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<=adj[0].size();j++){
                 ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:220:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int k=0;k<=adj[1].size();k++){
                   ~^~~~~~~~~~~~~~~
joi2019_ho_t3.cpp:224:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(i+1-(j+k)>adj[2].size()){
     ~~~~~~~~~^~~~~~~~~~~~~~

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