Submission #1040906

#TimeUsernameProblemLanguageResultExecution timeMemory
1040906StillOnQiCondensationKnapsack (NOI18_knapsack)C++14
73 / 100
118 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll; #define all(x) (x).begin(), (x).end() #define inf (ll)1000000007 #define llmax LLONG_MAX #define pi 3.141592653589793238462643383279502884197169399 long long binpow(long long a, long long b) { long long res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; } ll ncr(int n, int r) { if (n < r) return 0; long long p = 1, k = 1; if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; long long m = __gcd(p, k); p /= m; k /= m; n--; r--; } } else p = 1; return p; } vector <ll> vcreate(int n){ vector <ll> v(n); for (int i = 0; i < n; i++) { cin>>v[i]; } return v; } const int MOD=998244353; int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1}; ll ModExp(ll x, ll n, ll m) { assert(n >= 0); x %= m; // note: m * m must be less than 2^63 to avoid ll overflow ll res = 1; while (n > 0) { if (n % 2 == 1) { res = res * x % m; } x = x * x % m; n /= 2; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); //freopen("snakes.in", "r", stdin); //freopen("snakes.out", "w", stdout); /* ll T; cin>>T; for(ll oo=0; oo<T; oo++) { } */ int s{},n{}; cin>>s>>n; vector<pair<ll,pair<ll,ll>>> v(n); for(int i{0}; i<n; i++) { cin>>v[i].first>>v[i].second.first>>v[i].second.second; } sort(all(v)); reverse(all(v)); vector<pair<ll,ll>> ac; map<ll,int> m; for(int i{0}; i<n; i++) { for(int j{0}; j<v[i].second.second; j++) { if(m[v[i].second.first]>s/v[i].second.first)break; ac.push_back({v[i].first,v[i].second.first}); m[v[i].second.first]++; } } /* for(auto u: ac) { cout<<u.first<<" "<<u.second<<endl; } */ int k=ac.size(); vector<vector<ll>> dp(k+1,vll(s+1,0)); for(int i{0}; i<k; i++) { for(int j{0}; j<=s; j++) { dp[i+1][j]=max(dp[i+1][j],dp[i][j]); if(j>=ac[i].second) { dp[i+1][j]=max(dp[i+1][j],dp[i][j-ac[i].second]+ac[i].first); } } } ll ans{0}; for(int i{0}; i<=s; i++) { ans=max(ans,dp[k][i]); } /* for(int i{0}; i<=ac.size(); i++) { for(int j{0}; j<=s; j++) { cout<<dp[i][j]<<" "; } cout<<endl; } */ cout<<ans<<endl; }
#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...