結果

問題 No.54 Happy Hallowe'en
ユーザー tottoripaper
提出日時 2015-03-26 00:13:51
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 46 ms / 5,000 ms
コード長 1,869 bytes
コンパイル時間 715 ms
コンパイル使用メモリ 43,492 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-15 17:11:43
合計ジャッジ時間 1,968 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:98:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   98 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
main.cpp:101:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  101 |         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++){
        const P& p = ps[i].second;
        for(int j=0;j<p.first;j++){
            if(j+p.second > 20000){continue;}
            mx[j] = std::max(mx[j], mx[j+p.second]);
        }
    }
    
    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