Submission #1140800

#TimeUsernameProblemLanguageResultExecution timeMemory
1140800zyadhanyKnapsack (NOI18_knapsack)C++20
100 / 100
38 ms3276 KiB
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> #include <unordered_map> #include <unordered_set> #define ll long long #define ld long double #define pl pair<ll, ll> #define vi vector<ll> #define vii vector<vi> #define vc vector<char> #define vcc vector<vc> #define vp vector<pl> #define mi map<ll,ll> #define mc map<char,int> #define sortx(X) sort(X.begin(),X.end()); #define all(X) X.begin(),X.end() #define allr(X) X.rbegin(),X.rend() #define ln '\n' #define YES {cout << "YES\n"; return;} #define NO {cout << "NO\n"; return;} #define MUN {cout << "-1\n"; return;} using namespace std; const int MODE = 998244353; void solve(int tc) { ll n, k; cin >> k >> n; vector<vp> Y(k + 1); for (int i = 0; i < n; i++) { ll v, c, cnt; cin >> v >> c >> cnt; Y[c].push_back({v, cnt}); } vp X; for (int i = 1; i <= k; i++) { sortx(Y[i]); ll cnt = 0; while (cnt <= k / i && !Y[i].empty()) { cnt++; X.push_back({Y[i].back().first, i}); Y[i].back().second--; if (!Y[i].back().second) Y[i].pop_back(); } } vi dp(k + 1); for (auto [v, c] : X) { for (int i = k - c; i >= 0; i--) { dp[i + c] = max(dp[i + c], dp[i] + v); } } cout << *max_element(all(dp)); } int main() { ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int size = 1; // freopen("spainting.in", "r", stdin); // freopen("spainting.out", "w", stdout); // cin >> size; for (int i = 1; i <= size; i++) solve(i); }
#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...