結果
問題 | No.626 Randomized 01 Knapsack |
ユーザー |
![]() |
提出日時 | 2020-04-08 16:53:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 2,075 bytes |
コンパイル時間 | 3,985 ms |
コンパイル使用メモリ | 220,704 KB |
最終ジャッジ日時 | 2025-01-09 15:11:37 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 |
ソースコード
//Let's join Kaede Takagaki Fan Club !!#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);}