結果
問題 |
No.951 【本日限定】1枚頼むともう1枚無料!
|
ユーザー |
![]() |
提出日時 | 2020-08-27 08:22:20 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 291 ms / 2,000 ms |
コード長 | 2,262 bytes |
コンパイル時間 | 18,625 ms |
コンパイル使用メモリ | 304,536 KB |
最終ジャッジ日時 | 2025-01-13 15:13:22 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
#pragma GCC target("avx2,avx") #pragma GCC optimize("O3") #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; using namespace __gnu_pbds; using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pll = pair<long long, long long>; #define rep(i, n) for(int i = 0; i < (n); ++i) #define all(x) (x).begin(),(x).end() constexpr char ln = '\n'; constexpr long long MOD = 1000000007; //constexpr long long MOD = 998244353; template<class T1, class T2> inline bool chmax(T1 &a, T2 b) {if (a < b) {a = b; return true;} return false;} template<class T1, class T2> inline bool chmin(T1 &a, T2 b) {if (a > b) {a = b; return true;} return false;} inline int topbit(int x) {return x == 0 ? -1 : 31-__builtin_clz(x);} inline int topbit(long long x) {return x == 0 ? -1 : 63-__builtin_clzll(x);} inline int botbit(int x) {return x == 0 ? 32 : __builtin_ctz(x);} inline int botbit(long long x) {return x == 0 ? 64 : __builtin_ctzll(x);} inline int popcount(int x) {return __builtin_popcount(x);} inline int popcount(long long x) {return __builtin_popcountll(x);} void print() {cout << "\n";} template<class T, class... Args> void print(const T &x, const Args &... args) { cout << x << " "; print(args...); } /////////////////////////////////////////////////////////////////////////////////////////////////////////////// int dp[5050][5050][2]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin >> N >> K; vector<int> P(N),D(N); rep(i,N) cin >> P[i] >> D[i]; vector<int> idx(N); iota(all(idx),0); sort(all(idx),[&](int i, int j){return P[i]>P[j];}); rep(i,N+1) rep(j,K+1) rep(k,2) dp[i][j][k] = -1e9; dp[0][0][0] = 0; rep(i,N) { int u = idx[i]; rep(j,K+1) { rep(k,2) { if (dp[i][j][k]==-1e9) continue; chmax(dp[i+1][j][k],dp[i][j][k]); if (!k and j+P[u]<=K) chmax(dp[i+1][j+P[u]][k^1],dp[i][j][k]+D[u]); if (k) chmax(dp[i+1][j][k^1],dp[i][j][k]+D[u]); } } } int ans = 0; rep(j,K+1) rep(k,2) chmax(ans,dp[N][j][k]); cout << ans << ln; }