結果

問題 No.54 Happy Hallowe'en
ユーザー tottoripaper
提出日時 2015-03-24 15:32:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 315 ms / 5,000 ms
コード長 2,147 bytes
コンパイル時間 483 ms
コンパイル使用メモリ 43,748 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 17:11:17
合計ジャッジ時間 3,078 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:107:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  107 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:110:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  110 |         scanf("%d %d", V+i, T+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

// Wrongri-La Shower

#include <cstdio>
#include <algorithm>
#include <utility>

typedef std::pair<int,int> P;
typedef std::pair<int,P> Q;

int N;
int V[10000], T[10000];
int dp[1<<12][20001];

int solve(){
    Q ps[10000];

    for(int i=0;i<N;i++){
        ps[i] = std::make_pair(T[i]+V[i], std::make_pair(T[i], V[i]));
    }
    std::sort(ps, ps+N);
    std::reverse(ps, ps+N);
    
    int mx[20001];
    for(int i=0;i<=20000;i++){
        mx[i] = i;
    }

    for(int i=0;i<N;i++){
        // printf("[%d, %d\n", i, ps[i].second);
        const P& p = ps[i].second;
        for(int j=0;j<=20000;j++){
            if(j-p.second < 0){continue;}
            if(j < p.first || j-p.second < p.first){
                mx[j-p.second] = std::max(mx[j-p.second], mx[j]);
            }
            
        }

        // puts(std::string(40, '-').c_str());
        // for(int j=0;j<110;j++){
        //     printf("%d: %d\n", j, mx[j]);
        // }
    }
    
    return mx[0];
}

int rec(int state, int sum){
    if(dp[state][sum] != -1){return dp[state][sum];}

    int res = sum;
    for(int i=0;i<N;i++){
        if(state >> i & 1){continue;}
        if(sum >= T[i]){continue;}
        
        res = std::max(res, rec(state | (1 << i), sum + V[i]));
    }

    return dp[state][sum] = res;
}

// bitDP解 (弱)
int solve1(){
    for(int i=0;i<1<<N;i++){
        for(int j=0;j<=20000;j++){
            dp[i][j] = -1;
        }
    }
    return rec(0, 0);
}

// T[i]基準解 (嘘)
int solve2(){
    P ps[10000];
    for(int i=0;i<N;i++){
        ps[i] = std::make_pair(T[i], V[i]);
    }

    std::sort(ps, ps+N);

    int sum = 0;
    for(int i=0;i<N;i++){
        if(sum < ps[i].first){sum += ps[i].second;}
    }

    return sum;
}

// V[i]基準解 (嘘)
int solve3(){
    P ps[10000];
    for(int i=0;i<N;i++){
        ps[i] = std::make_pair(V[i], T[i]);
    }

    std::sort(ps, ps+N);

    int sum = 0;
    for(int i=0;i<N;i++){
        if(sum < ps[i].second){sum += ps[i].first;}
    }

    return sum;
}

int main(){
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%d %d", V+i, T+i);
    }

    printf("%d\n", solve());
}
0