Submission #1263006

#TimeUsernameProblemLanguageResultExecution timeMemory
1263006khanghb2006Knapsack (NOI18_knapsack)C++20
100 / 100
188 ms33256 KiB
#include<bits/stdc++.h> using namespace std; #define TASK "task" const int mxN = 2e3 + 7; const int inf = 1e9 + 67; int n; int s; long long dp[mxN][mxN]; vector<pair<int,int>>groups[mxN]; void solve(void) { cin >> s >> n; for (int i = 1; i <= n; i++) { int v , w , k; cin >> v >> w >> k; groups[w].push_back(make_pair(v , k)); } for (int i = 0; i <= s; i++) sort(groups[i].begin() , groups[i].end() , greater<pair<int,int>>()); for (int i = 1; i <= s; i++) { for (int j = 0; j <= s; j++) dp[i][j] = dp[i - 1][j]; if(!groups[i].size()) continue; // với cân nặng i thì chỉ có thể lấy nhiều nhất S / i cái for (int j = s; j >= 0; j--) { int w = 0; long long v = 0; for (auto it : groups[i]) { int k = it.second; while(k > 0 && w <= j) { w += i; v += it.first; --k; if(j >= w) dp[i][j] = max(dp[i][j] , dp[i - 1][j - w] + v); } } } } long long ans = -inf; for (int i = 0; i <= s; i++) for (int j = 0; j <= s; j++) ans = max(ans , dp[i][j]); cout << ans; } int main() { ios_base :: sync_with_stdio(0); cin.tie(0); //freopen(TASK".inp","r",stdin); //freopen(TASK".out","w",stdout); int tc = 1; //cin >> tc; while(tc--) solve(); return 0; }
#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...