結果
問題 | No.2869 yuusaan's Knapsacks |
ユーザー |
👑 ![]() |
提出日時 | 2024-08-30 22:16:10 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 4,500 ms |
コード長 | 1,665 bytes |
コンパイル時間 | 1,162 ms |
コンパイル使用メモリ | 87,236 KB |
最終ジャッジ日時 | 2025-02-24 03:07:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#ifdef NACHIA #define _GLIBCXX_DEBUG #else #define NDEBUG #endif #include <iostream> #include <string> #include <vector> #include <algorithm> #include <tuple> using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<int(n); i++) const i64 INF = 1001001001001001001; template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; } template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; } #include <atcoder/modint> using Modint = atcoder::static_modint<998244353>; using namespace std; void testcase(){ i64 N, M; cin >> N >> M; vector<tuple<i64,i64,i64>> dp(1<<M, {N,0,-1}); dp[0] = {0,0,-1}; vector<i64> E(N); rep(i,N) cin >> E[i]; vector<i64> V(M), W(M); rep(i,M) cin >> V[i] >> W[i]; pair<i64,i64> maxvalue = { 0,0 }; rep(i,1<<M){ auto [a,b,pre] = dp[i]; if(a == N) continue; i64 vsum = 0; rep(c,M){ if((i&(1<<c)) == 0){ i64 ax = a; i64 bx = b + W[c]; while(ax < N && E[ax] < bx){ ax++; bx = W[c]; } chmin(dp[i|(1<<c)], make_tuple(ax, bx, i64(c))); } else vsum += V[c]; } chmax(maxvalue, make_pair(vsum, i64(i))); } vector<vector<i64>> ans(N); i64 p = maxvalue.second; while(p){ auto [a,b,c] = dp[p]; ans[a].push_back(c); p -= 1 << c; } cout << maxvalue.first << endl; rep(i,N){ cout << ans[i].size(); for(auto a : ans[i]){ cout << ' ' << (a+1); } cout << endl; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); testcase(); return 0; }