제출 #945564

#제출 시각아이디문제언어결과실행 시간메모리
945564nasir_bashirovKnapsack (NOI18_knapsack)C++17
29 / 100
2 ms504 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define db long double #define ll long long #define pii pair<int, int> #define pll pair<ll, ll> #define vi vector<int> #define vl vector<ll> #define vii vector<pii> #define vll vector<pll> #define endl '\n' #define all(x) x.begin(), x.end() #define fastio\ ios_base::sync_with_stdio(0);\ cin.tie(0);\ cout.tie(0)\ #define int long long int dp[2005], n, m, x, y, z; vii w[2005]; signed main(){ fastio; cin >> m >> n; for(int i = 1; i <= n; i++){ cin >> x >> y >> z; w[y].push_back({x, z}); } for(int i = 1; i <= m; i++){ sort(all(w[i])); reverse(all(w[i])); } for(int i = 1; i <= m; i++){ for(int j = m; j >= 1; j--){ int cur = 0, tot = 0; for(pii z : w[i]){ if(z.second * i + cur <= j) cur += z.second * i, tot += z.first * z.second; else tot += ((j - cur) / i) * z.first, cur += ((j - cur) / i) * i; dp[j] = max(dp[j], dp[j - cur] + tot); } } } cout << dp[m]; }
#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...