Submission #678438

#TimeUsernameProblemLanguageResultExecution timeMemory
678438whaaaaKnapsack (NOI18_knapsack)C++11
12 / 100
1 ms340 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 int #define all(x) x.begin(), x.end() #define pi pair<int,int> #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() { int s, n; cin >> s >> n; // cout << "hey" << endl; vector<vector<pi>> a(s+1); for(int i = 0; i < n; i++){ int aa,b,c; cin >> aa >> b >> c; a[b].pb({aa,c}); } for(int i = 1; i <= s; i++){ sort(all(a[i]), comp); } vector<int> dp(s+1); vector<pi> used(s+1, {0,0}); // cout << "hey" << endl; for(int i = 1; i <= s; i++){ // cout << i << endl; if(a[i].empty()) continue; vector<int> dp2 = dp; vector<pi> used2(s+1, {0,0}); for(int 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()){ 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(used2[j].f < a[i].size()){ if(dp[j+i] < dp2[j] + a[i][used2[j].f].f){ used2[j+i] = {used2[j].f, used2[j].sec+1}; dp[j+1] = dp2[j] + a[i][used2[j].f].f; } }*/ } // cout << endl; used = vector<pi>(s+1, {0,0}); } int ans = 0; for(int x = 0; x <= s; x++){ ans = max(ans, dp[x]); } cout << ans; }

Compilation message (stderr)

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