結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2020-04-08 16:53:28 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 7 ms / 2,000 ms |
コード長 | 2,220 bytes |
コンパイル時間 | 17,201 ms |
コンパイル使用メモリ | 303,700 KB |
最終ジャッジ日時 | 2025-01-09 15:11:26 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
//Let's join Kaede Takagaki Fan Club !! #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; typedef long long ll; typedef pair<int,int> P; typedef pair<int,P> P1; typedef pair<P,P> P2; #define pu push #define pb push_back #define mp make_pair #define eps 1e-7 #define INF 1000000000 #define fi first #define sc second #define rep(i,x) for(int i=0;i<x;i++) #define repn(i,x) for(int i=1;i<=x;i++) #define SORT(x) sort(x.begin(),x.end()) #define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end()) #define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) #define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) #define all(x) x.begin(),x.end() template<class T> void dmp(T a){ rep(i,a.size()) cout << a[i] << " "; cout << endl; } template<class T> bool chmax(T&a, T b){ if(a < b){ a = b; return 1; } return 0; } template<class T> bool chmin(T&a, T b){ if(a > b){ a = b; return 1; } return 0; } template<class T> void g(T &a){ cin >> a; } template<class T> void o(const T &a,bool space=false){ cout << a << (space?' ':'\n'); } //ios::sync_with_stdio(false); const ll mod = 998244353; template<class T> void add(T&a,T b){ a+=b; if(a >= mod) a-=mod; } int n; ll v[5005], w[5005], lim; vector<pair<ll,ll>>item; ll ret; void rec(int pt, ll cur, ll val){ if(pt == item.size()) return; ll zan = lim - cur, relax = val; for(int i=pt;i<item.size();i++){ if(zan >= item[i].sc){ zan -= item[i].sc; relax += item[i].fi; } else{ relax += ((__int128)(zan) * item[i].fi + item[i].sc - 1) / item[i].sc; break; } } if(relax <= ret) return; if(cur + item[pt].sc <= lim){ chmax(ret, val + item[pt].fi); rec(pt+1, cur + item[pt].sc, val + item[pt].fi); } rec(pt+1, cur, val); } int main(){ ios::sync_with_stdio(false); g(n); g(lim); rep(i,n){ cin >> v[i] >> w[i]; item.pb(mp(v[i], w[i])); } sort(item.begin(), item.end(), [&](pair<ll,ll>a, pair<ll,ll>b){ return (__int128)(a.fi) * b.sc > (__int128)(b.fi) * a.sc; }); rec(0, 0, 0); o(ret); }