結果
問題 | No.2232 Miser's Gift |
ユーザー |
![]() |
提出日時 | 2023-03-03 21:37:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 147 ms / 2,000 ms |
コード長 | 760 bytes |
コンパイル時間 | 9,214 ms |
コンパイル使用メモリ | 273,924 KB |
最終ジャッジ日時 | 2025-02-11 02:03:34 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 55 |
ソースコード
#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, W; cin >> N >> W; vector<int> dp(W+1), ep(W+1); for( int i = 0; i < N; i++ ) { int w, v; cin >> w >> v; for( int j = 0; j <= W; j++ ) { ep[j] = max(ep[j], dp[j]); if( 0 <= j-w ) { ep[j] = max(ep[j], dp[j-w]+v); } } for( int j = 1; j <= W; j++ ) { ep[j] = max(ep[j], ep[j-1]); } swap(dp, ep); fill(ep.begin(), ep.end(), 0); } for( int X = 1; X <= W; X++ ) { int l = 0, r = 1000000005, m; while( l < r-1 ) { m = (l+r)>>1; if( dp[W-X]+m > dp[W] ) { r = m; }else { l = m; } } cout << r << endl; } }