SRM602 div2 Med PilingRectsDiv2

問題読み間違えて詰んでた

問題概要

・幅Xi高さYiの長方形がN個ある
・面積がlimit以上となるように長方形を重ねる(はみ出して良い、はみ出したらいけないと思っていた)
・90度回転して良い
・最大で何枚重ねられるか

方針

まず幅>高さとなるようにし、幅で昇順に並び替える。重ねる長方形の最小の幅を固定し重ねた時にlimitを超えるかどうか調べる。超えるなら重ねる。

最小の幅がO(N)。それぞれの最小の幅について幅が最小の幅以上の長方形についてlimitを超えるかどうかの計算でO(N)。よって計算量はO(N²)。

コード

typedef pair<int, int> P;
class PilingRectsDiv2 {
public:
  int getmax(vector <int> X, vector <int> Y, int limit) {
    int n = X.size();
    vector<P> v(n);
    FOR(i,0,n) {
      if(X[i] < Y[i]) swap(X[i], Y[i]);
      v[i] = P(X[i], Y[i]);
    }
    sort(v.begin(), v.end());
    int ans = -1;
    FOR(i,0,n) {
      int cnt = 0;
      FOR(j,i,n) if(v[i].first * min(v[i].second, v[j].second) >= limit) cnt++;
      if(cnt) ans = max(ans, cnt);
    }
    return ans;
  }
};

英語難しい