Submission #8316658

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}

int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x;}

struct BIT {
  using Val = int;
  int n;
  vector<Val> tree;
  BIT(int n):n(n),tree(n+1) {}
  void fill(Val val) {
    REP(i, n+1) tree[i] = (i&-i) * val;
  }
  void add(int idx, Val val) {
    for (int x=idx+1; x<=n; x+=x&-x) tree[x] += val;
  }
  // sum[0, idx]
  Val range(int idx) {
    Val sum=0;
    for (int x=idx+1; x>0; x-=x&-x) sum += tree[x];
    return sum;
  }
};

const int INF = 1001001001;
const int MAX_N = 2005;
int dp[MAX_N][MAX_N];
int idx_b[MAX_N];
int idx_w[MAX_N];
int bb[2*MAX_N][MAX_N]; // bb[i][j] := 元の列のi番目より左にある B のうち番号が j より大きいものの個数。
int ww[2*MAX_N][MAX_N];

int main2() {
  int N = nextInt();
  vector<char> c(2*N);
  vector<int> a(2*N);

  REP(i, 2*N) {
    cin >> c[i] >> a[i];
    if (c[i] == 'B') {
      idx_b[a[i]] = i;
    } else {
      idx_w[a[i]] = i;
    }
  }

  {
    CLR(bb, 0);
    BIT bit(2*N+10);
    int s = 0;
    REP(i, 2*N) {
      if (c[i] == 'B') {
        bit.add(a[i], 1);
        s++;
      }
      for (int j = 0; j <= N; j++) {
        bb[i][j] = s - bit.range(j);
      }
    }
  }
  {
    CLR(ww, 0);
    BIT bit(2*N+10);
    int s = 0;
    REP(i, 2*N) {
      if (c[i] == 'W') {
        bit.add(a[i], 1);
        s++;
      }
      for (int j = 0; j <= N; j++) {
        ww[i][j] = s - bit.range(j);
      }
    }
  }

  REP(i, MAX_N) REP(j, MAX_N) dp[i][j] = INF;
  dp[0][0] = 0;
  REP(w, N+1) REP(b, N+1) {
    if (w == 0 && b == 0) continue;
    int val = INF;
    if (w - 1 >= 0) {
      int i = idx_w[w];
      int cost = bb[i][b] + ww[i][w];
      chmin(val, dp[w-1][b] + cost);
    }
    if (b - 1 >= 0) {
      int i = idx_b[b];
      int cost = bb[i][b] + ww[i][w];
      chmin(val, dp[w][b-1] + cost);
    }
    dp[w][b] = val;
  }
  int ans = dp[N][N];
  cout << ans << endl;
  return 0;
}

int main() {

#ifdef LOCAL
  for (;!cin.eof();cin>>ws)
#endif
    main2();
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int nextInt()’:
./Main.cpp:13:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int nextInt() { int x; scanf("%d", &x); return x;}
                                       ^
./Main.cpp: In function ‘ll nextLong()’:
./Main.cpp:14:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll nextLong() { ll x; scanf("%lld", &x); return x;}
                                        ^

Judge Result