제출 #982012

#제출 시각아이디문제언어결과실행 시간메모리
982012Amirreza_FakhriKnapsack (NOI18_knapsack)C++17
12 / 100
8 ms27228 KiB
// In the name of the God #include <bits/stdc++.h> #define ll long long #define int long long #define pb push_back #define F first #define S second #define mp make_pair #define pii pair <int, int> #define smin(x, y) (x) = min((x), (y)) #define smax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(), (x).end() using namespace std; // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2") const int inf = 1e9+7; const int mod = 998244353; const int maxw = 2e3+5, maxv = 1e6+5; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int s, n, dp[maxw*15][maxw]; vector <pii> va[maxv]; vector <int> we[maxw]; int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> s >> n; for (int i = 0; i < n; i++) { int v, w, k; cin >> v >> w >> k; va[v].pb(mp(w, k)); // while (k--) we[w].pb(v); } for (int i = 1; i < maxv; i++) { for (pii p : va[i]) { int w = p.F, k = p.S; int left = s/w-we[w].size(); while (left and k) { we[w].pb(i); left--, k--; } } } int cnt = 1; for (int i = 1; i <= s; i++) { for (int j : we[i]) { for (int k = 1; k <= s; k++) { dp[cnt][k] = dp[cnt-1][k]; if (i <= k) { smax(dp[cnt][k], dp[cnt-1][k-i]+j); } } cnt++; } } cout << dp[cnt-1][s] << '\n'; return 0; } /* srand(time(0)); cout << (rand()%1900) + 1 << ' ' << (rand()%2)+5 << '\n'; */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...