Submission #1040866

#TimeUsernameProblemLanguageResultExecution timeMemory
1040866StillOnQiCondensationKnapsack (NOI18_knapsack)C++14
49 / 100
15 ms31832 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; } */ vector<vector<ll>> dp(ac.size()+1,vll(s+1,0)); for(int i{0}; i<ac.size(); 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<=s) { dp[i+1][j+ac[i].second]=max(dp[i+1][j+ac[i].second],dp[i][j]+ac[i].first); } } } ll ans{0}; for(int i{0}; i<=s; i++) { ans=max(ans,dp[ac.size()][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; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:114:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for(int i{0}; i<ac.size(); 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...