Codeforces Round #297 (Div. 2) C. Ilya and Sticks
Codeforces Round #297 (Div. 2)に参加しました。C問題を誤読しててそれに大半の時間を使ったためにボロボロでした。
問題:http://codeforces.com/contest/525/problem/C
解法:できるだけ長い辺と長い辺を組み合わせて長方形を作るのが最適。ということでそうなるように貪欲に辺を取っていけば良い。
本番は「長方形の合計の面積を最大化」でなく「1つの長方形の面積を最大化」だと思って時間を食った。CodeForcesはコンテストの形式上TopCoderに比べてサンプルが問題文を完全に表現してないことが多いのでよく読まないとダメだね。
以下ソースコード
const int MAXN = 100100; const int MAXL = 1001000; ll l[MAXN]; int num[MAXL]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> l[i]; num[l[i]]++; } vector<ll> p; for (ll i = MAXL-2; i >= 1; i--) { if (num[i] > 0) { if (num[i+1] > 0) { num[i+1]--; num[i]--; p.push_back(i); } if (num[i] > 0) { while (num[i] > 1) { p.push_back(i); num[i] -= 2; } } } } sort(p.begin(), p.end()); reverse(p.begin(), p.end()); ll ans = 0; for (int i = 0; i < (int)p.size(); i+=2) { if (i+1 >= (int)p.size()) break; ans += p[i]*p[i+1]; } cout << ans << endl; return 0; }