Submission #3664659

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,k;
int a[5252], b[5252];
int reva[5252];
int revb[5252];
bool used[5252];

int dp1[5252][2][2][5252];

int naive(){
  int ans = 0;
  REP(msk,1<<n){
    int tmp = 0;
    set<int> S;
    REP(i,n)if((msk>>i)&1){
      S.insert(a[i]); tmp+=a[i];
    }else{
      S.insert(b[i]); tmp+=b[i];
    }
    if(S.size() >= k){
      CHMAX(ans, tmp);
    }
  }return ans;
}

int main(){
  scanf("%d%d",&n,&k);
  REP(i,n)scanf("%d",a+i);
  REP(i,n)scanf("%d",b+i);
  // n = 4; k = 3;
  // REP(i,n)a[i]=b[i]=i+1;
  // srand(time(NULL));
  // random_shuffle(a,a+n);
  // random_shuffle(b,b+n);
  
  REP(i,n+1)reva[i] = revb[i] = -1;
  REP(i,n)revb[b[i]] = i;
  REP(i,n)reva[a[i]] = i;
  FOR(i,1,n+1)assert(reva[i]!=-1 && revb[i]!=-1);

  vi dp(1,0);
  REP(i,n)if(!used[i]){
    used[i] = true;
    if(a[i]==b[i]){
      int m = dp.size();
      vi ndp(m+1,-1e9);
      REP(j,m)ndp[j+1] = dp[j] + a[i];
      dp = ndp;
    }else{
      // loop
      vector<pii> l;
      int c = i;
      while(true){
        l.push_back(pii(a[c], b[c]));
        used[c] = true;
        c = reva[b[c]];
        if(c==i)break;
      }
      int m = l.size();
      vi dp2(m+1,-1e9);

      if(m==2){
        dp2[1] = 2 * max(l[0].first, l[0].second);
        dp2[2] = l[0].first + l[0].second;
      }else{
        REP(i,m+1)REP(j,2)REP(k,2)REP(l,m+1)dp1[i][j][k][l] = -1e9;
        dp1[1][0][0][1] = l[0].first;
        dp1[1][1][1][1] = l[0].second;
        FOR(i,1,m)REP(j,2)REP(k,2)REP(kind,m+1)if(dp1[i][j][k][kind]>=0){
          // use first
          CHMAX(dp1[i+1][j][0][kind + (k==0?1:0)], dp1[i][j][k][kind]+l[i].first);
          // use second
          if(i==m-1){
            CHMAX(dp1[i+1][j][1][kind + (j==1?1:0)], dp1[i][j][k][kind]+l[i].second);
          }else{
            CHMAX(dp1[i+1][j][1][kind+1], dp1[i][j][k][kind]+l[i].second);
          }
        }
        REP(i,m+1){
          CHMAX(dp2[i], dp1[m][0][0][i]);
          CHMAX(dp2[i], dp1[m][0][1][i]);
          CHMAX(dp2[i], dp1[m][1][0][i]);
          CHMAX(dp2[i], dp1[m][1][1][i]);
        }
        // FORR(i,0,m)CHMAX(dp2[i], dp2[i+1]);
        // DEBUG_VEC(dp2);
      }

      // int sum = 0;
      // REP(i,m)sum+=l[i].first;
      // vi sa;
      // REP(i,m)sa.push_back(l[i].first - l[i].second);
      // sort(ALL(sa));

      // int lv=0, rv=0;
      // REP(i,m){
      //   CHMAX(dp2[m-i], sum+lv);
      //   CHMAX(dp2[m-i], sum+rv);
      //   lv -= sa[i];
      //   rv += sa[m-1-i];
      // }

      // convolution
      int m2 = dp.size();
      vi ndp(m+m2,-1e9);
      REP(i,m+1)REP(j,m2){
        CHMAX(ndp[i+j],dp[j]+dp2[i]);
      }
      dp = ndp;
    }
  }
  // DEBUG_VEC(dp);
  int m = dp.size();
  int ans = 0;
  FOR(i,k,m)CHMAX(ans, dp[i]);

  // int nnn = naive();
  // if(ans != nnn){
  //   DEBUG("ERROR");
  //   printf("%d %d\n",n,k);
  //   REP(i,n)printf("%d ",a[i]);puts("");
  //   REP(i,n)printf("%d ",b[i]);puts("");
  //   printf("ans : %d\n",ans);
  //   printf("nnn : %d\n",nnn);
  //   return 0;
  // }

  printf("%d\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:59:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&k);
                      ^
./Main.cpp:60:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,n)scanf("%d",a+i);
                          ^
./Main.cpp:61:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(i,n)scanf("%d",b+i);
                          ^

Judge Result