問題文に記載の通りの操作を実際に行おうとすると、次のようなケースで 本 1 冊あたり \(\Omega(M)\) 時間、全体で \(\Omega(NM)\) 時間かかり、実行時間制限に間に合わせることは困難です。

200000 200000
200000 199999 199998 ... 3 2 1
1 2 3 ... 199998 199999 200000

本を挿入する箇所を二分探索できないか考えます。
「スペース \(x\) までにこの本を入れることができる箇所はあるか？」を判定するためには、「スペース \(1,2,\dots, x\) のうちまだ本が置かれていないものの耐荷重の最大値」がわかれば十分です。また既に本が置かれたスペースは耐荷重を \(0\) に置き換えることで無視することができます。

よって、区間最大値取得と 1 点更新を高速に行えるデータ構造があればよいことがわかりました。これはセグメントツリーにより実現できます。

ACL のセグメントツリーには二分探索のための機能が存在するため、これを適切に利用することでこの問題を \(O((N+M)\log N)\) で解くことができます。

実装例 (C++)

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

int main(){
  int n, m;
  cin >> n >> m;
  vector<int> w(n);
  for(int i=0; i<n; i++) cin >> w[i];
  vector<int> c(m);
  for(int i=0; i<m; i++) cin >> c[i];
  
  auto e = [](){return 0;};
  auto op = [](int x, int y){return max(x, y);};
  
  atcoder::segtree<int, op, e> seg(c);
  
  int ans = 0;
  for(int i=0; i<n; i++){
    auto f = [&](int x){return x < w[i];};
    int r = seg.max_right(0, f);
    if(r != m){
      ans++;
      seg.set(r, 0);
    }
  }
  cout << ans << endl;
}

実装例 (Python)

from atcoder.segtree import SegTree

N, M = map(int,input().split())
W = list(map(int,input().split()))
C = list(map(int,input().split()))

seg = SegTree(max, 0, C)
ans = 0
for w in W:
  f = lambda x: x < w
  r = seg.max_right(0, f)
  if r != M:
    ans += 1
    seg.set(r, 0)

print(ans)