Submission #945579

#TimeUsernameProblemLanguageResultExecution timeMemory
945579nasir_bashirovKnapsack (NOI18_knapsack)C++11
37 / 100
1035 ms604 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])); while(w[i].size() > m / i) w[i].pop_back(); } for(int i = 1; i <= m; i++){ for(pii j : w[i]){ for(int z = 1; z <= j.second; z++){ for(int k = m; k >= i; k--){ dp[k] = max(dp[k], dp[k - i] + j.first); } } } } cout << dp[m]; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:37:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   37 |         while(w[i].size() > m / i)  w[i].pop_back();
      |               ~~~~~~~~~~~~^~~~~~~
#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...