558A - Lala Land and Apple Trees

Problem - A - Codeforces

• 復習。本番通ったけどコードが汚かったので書き直し。無駄に dfs とかしてたけど単なる足し算で住む話だった。
• 書き直しして WA になったりしたあたり本当に実装力が足りないと思った。

class Div2A {
public:
    void solve(void) {
            int N;
            cin>>N;
            using Tree = pair<int,int>;
            #define X(t) ((t).first)
            #define nApple(t) ((t).second)
            vector<Tree> L;
            vector<Tree> R;
            REP(i, N)
            {
                int x, a;
                cin>>x>>a;
                if (x > 0)
                    R.emplace_back(x,a);
                else
                    L.emplace_back(x,a);
            }
            // O(N*log(N))
            // x の位置で原点に近い順にソートする。ないとは思うけど同じ位置に木が二本生えているときは
            // りんごの数が多いほうを原点に近くなるようにする
            sort(RANGE(R), [](const Tree &a, const Tree &b)->bool {
                    return (X(a)==X(b))? nApple(b)<nApple(a) : X(a)<X(b);
                });
            sort(RANGE(L), [](const Tree &a, const Tree &b)->bool {
                    return (X(a)==X(b))? nApple(b)<nApple(a) : X(b)<X(a);
                });

            auto sum = [](const vector<Tree> &ts, int n)->int {
                return accumulate(ts.begin(), ts.begin()+n, 0,
                                  [](int s, const Tree& t)->int { return s+nApple(t); });
            };
            int ans = 0;
            // O(N)
            if (L.size() == R.size())
            {
                ans += sum(L, L.size());
                ans += sum(R, R.size());
            }
            else if (L.size() < R.size())
            {   // R 方向から始めて +1 本多く見る
                ans += sum(L, L.size());
                ans += sum(R, L.size()+1);
            }
            else
            {
                ans += sum(R, R.size());
                ans += sum(L, R.size()+1);
            }
            cout<<ans<<endl;
    }
};