Submission #767232

#TimeUsernameProblemLanguageResultExecution timeMemory
767232synthesisKnapsack (NOI18_knapsack)C++17
12 / 100
35 ms6480 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define fi first #define se second #define pii pair<int, int> #define pb push_back #define vi vector<int> #define all(x) x.begin(), x.end() using namespace std; using namespace __gnu_pbds; using ll = long long int; using ull = unsigned long long int; constexpr ll mod = 1e9 + 7; constexpr ll INF = LONG_LONG_MAX; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; string moves = "URDL"; int main() { //tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> q; /*freopen("problemname.in", "r", stdin); freopen("problemname.out", "w", stdout);*/ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int s, n; cin >> s >> n; map<int, vector<int>> t; for(int i = 0;i<n;++i) { int x, y, z; cin >> x >> y >> z; while(t[y].size() <= s && z--) { t[y].pb(x); } } for(auto& [x, y]:t) { vi c = y; sort(all(c)); reverse(all(c)); t[x] = c; } int dp[s + 1][s + 1], ans = 0; memset(dp, 0, sizeof dp); for(int i = 1;i<=s;++i) { for(int j = 0;j<=s;++j) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); int cnt = 1, siz = t[i].size(), val = 0; while(cnt <= siz && j - cnt*i >= 0) { val+=t[i].at(cnt - 1); dp[i][j] = max(dp[i][j], dp[i - 1][j - cnt*i] + val); ++cnt; } ans = max(ans, dp[i][j]); } } cout << ans << endl; return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:36:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while(t[y].size() <= s && z--) {
      |               ~~~~~~~~~~~~^~~~
#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...