結果

問題 No.3401 Large Knapsack Problem
コンテスト
ユーザー Mike scarf
提出日時 2025-12-12 15:49:00
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 831 ms / 2,000 ms
コード長 712 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,806 ms
コンパイル使用メモリ 274,984 KB
実行使用メモリ 160,076 KB
最終ジャッジ日時 2025-12-12 15:49:35
合計ジャッジ時間 33,792 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 42
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:12:28: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   12 |     for(i=1;i<=n;i++) scanf("%lld%lld",&v[i],&w[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf=1e18;
const int maxn=20000005;
ll n,wc,v[25],w[25],dp[maxn];
int main(){
    ll ans,lm,id;
    int i,j;
    ans=0; lm=20000000; id=1;
    if(scanf("%lld%lld",&n,&wc)!=2) return 0;
    for(i=1;i<=n;i++) scanf("%lld%lld",&v[i],&w[i]);
    for(i=2;i<=n;i++) if(v[i]*w[id]>v[id]*w[i]) id=i;
    if(wc<lm) lm=wc;
    for(i=1;i<=lm;i++) dp[i]=-1;
    for(i=0;i<=lm;i++){
        if(dp[i]==-1) continue;
        for(j=1;j<=n;j++) if(i+w[j]<=lm) dp[i+w[j]]=max(dp[i+w[j]],dp[i]+v[j]);
    }
    for(i=0;i<=lm;i++){
        if(dp[i]==-1) continue;
        ans=max(ans,dp[i]+(wc-i)/w[id]*v[id]);
    }
    printf("%lld\n",ans);
    return 0;
}
0