結果

問題 No.54 Happy Hallowe'en
コンテスト
ユーザー codershifth
提出日時 2015-08-21 00:10:44
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 169 ms / 5,000 ms
コード長 2,443 bytes
コンパイル時間 1,351 ms
コンパイル使用メモリ 166,668 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 17:13:35
合計ジャッジ時間 2,870 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class HappyHalloween {
public:
    void solve(void) {
            int N;
            cin>>N;

            int maxT = 0;
            int maxV = 0;
            vector<pair<int,int>> candy;
            REP(i,N)
            {
                int v,t;
                cin>>v>>t;
                maxT = max(maxT,t);
                maxV = max(maxV,v);
                candy.emplace_back(v,t);
            }
            // 現在の candy の個数を C とするとき
            // C < T[a], C < T[b] として家 a, b を訪れるケースを考える。
            // a,b どちらが先でもキャンディをもらえるならどちらの順でもよいが、
            // そうでないケースを考える
            //
            // 1. a -> b 順でキャンディがもらえるとき C+V[a] < T[b]
            // 2. b -> a 順ではキャンディがもらえないとい C+V[b] >= T[a]
            //
            // 1,2 が同時に成り立つときは
            //
            // V[a]+T[a] < V[b]+T[b]
            //
            // となる。よって V[i]+T[i] でソートした順訪れれば良い。
            //

            // O(N*log(N))
            sort(RANGE(candy), [](const pair<int,int> &a, const pair<int,int> &b){
                    return a.first+a.second < b.first+b.second;
                });

            // dp[C] := キャンディを C 個もらえるか？
            vector<bool> dp(maxV+maxT+1,false);

            // O(N*maxT)
            dp[0] = true;
            REP(i,N)
            {
                int v = candy[i].first;
                // i のときの dp 更新を伝播させないために逆順にやる
                // C < T[i] のときしかもらえないので T[i]-1 から
                for (int C = candy[i].second-1; C >= 0; --C)
                    dp[v+C] = dp[v+C] | dp[C];
            }

            int C;
            for (C = dp.size()-1; C >= 0; --C)
                if (dp[C])
                    break;
            cout<<C<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new HappyHalloween();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0