Submission #678446

#TimeUsernameProblemLanguageResultExecution timeMemory
678446whaaaaKnapsack (NOI18_knapsack)C++14
12 / 100
2 ms468 KiB
#include <iostream> #include <cstdio> #include <algorithm> #include <math.h> #include <utility> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <stack> #define ll long long #define itn ll #define all(x) x.begin(), x.end() #define pi pair<ll,ll> #define f first #define sec second #define fr front() #define pb push_back using namespace std; bool comp(pi a, pi b){ return a.f > b.f; } int main() { ll s, n; cin >> s >> n; // cout << "hey" << endl; vector<vector<pi>> a(s+1); for(ll i = 0; i < n; i++){ ll aa,b,c; cin >> aa >> b >> c; a[b].pb({aa,c}); } for(ll i = 1; i <= s; i++){ sort(all(a[i]), comp); } vector<ll> dp(s+1, -1); dp[0] = 0; vector<pi> used(s+1, {0,0}); // cout << "hey" << endl; for(ll i = 1; i <= s; i++){ //cout << i << endl; if(a[i].empty()) continue; vector<ll> dp2 = dp; vector<pi> used2(s+1, {0,0}); bool do1 = true, do2 = true; for(ll j = 0; j <= s; j++){ //cout << "\t" << j << endl; if(j + i > s) break; if(used[j].sec >= a[i][used[j].f].sec){ used[j].sec = 0; used[j].f++; } if(used2[j].sec >= a[i][used2[j].f].sec){ used2[j].sec = 0; used2[j].f++; } if(used[j].f >= a[i].size()) do1 = false; if(used2[j].f >= a[i].size()) do2 = false; if(do1 && dp[j] != -1){ if(dp[j+i] < dp[j] + a[i][used[j].f].f){ used[j+i] = {used[j].f, used[j].sec+1}; dp[j+i] = dp[j] + a[i][used[j].f].f; } } if(do2 && dp2[j] != -1){ if(dp[j+i] < dp2[j] + a[i][used2[j].f].f){ used2[j+i] = {used2[j].f, used2[j].sec+1}; dp[j+i] = dp2[j] + a[i][used2[j].f].f; } } } used = vector<pi>(s+1, {0,0}); used2 = used; } ll ans = 0; for(ll x = 0; x <= s; x++){ // cout << x << ": " << dp[x] << endl; if(dp[x] > ans){ ans = dp[x]; } } cout << ans; }

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:62:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if(used[j].f >= a[i].size()) do1 = false;
knapsack.cpp:63:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             if(used2[j].f >= a[i].size()) do2 = false;
#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...