結果
問題 | No.1947 質より種類数 |
ユーザー |
![]() |
提出日時 | 2022-05-21 02:18:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 993 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 43,072 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-09-20 11:00:00 |
合計ジャッジ時間 | 5,702 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 29 TLE * 1 -- * 7 |
ソースコード
/* -*- coding: utf-8 -*- * * 1947.cc: No.1947 質より種類数 - yukicoder */ #include<cstdio> #include<algorithm> using namespace std; /* constant */ const int MAX_N = 5000; const int MAX_V = 5000; /* typedef */ typedef long long ll; /* global variables */ ll dp[2][MAX_V + 1]; /* subroutines */ inline void setmax(ll &a, ll b) { if (a < b) a = b; } /* main */ int main() { int n, v, c; scanf("%d%d%d", &n, &v, &c); fill(dp[0], dp[0] + v + 1, -1); dp[0][0] = 0; int cur = 0, nxt = 1; for (int i = 0; i < n; i++) { int vi, wi; scanf("%d%d", &vi, &wi); copy(dp[cur], dp[cur] + v + 1, dp[nxt]); int kv = vi, kw = c + wi; while (kv <= v) { int maxj = v - kv; for (int j = 0; j <= maxj; j++) if (dp[cur][j] >= 0) setmax(dp[nxt][j + kv], dp[cur][j] + kw); kv += vi, kw += wi; } swap(cur, nxt); } ll maxd = 0; for (int j = 0; j <= v; j++) setmax(maxd, dp[cur][j]); printf("%lld\n", maxd); return 0; }