제출 #923826

#제출 시각아이디문제언어결과실행 시간메모리
923826KarootKnapsack (NOI18_knapsack)C++17
100 / 100
142 ms258964 KiB
#include <iostream> #include <cmath> #include <unordered_map> #include <map> #include <set> #include <queue> #include <vector> #include <string> #include <iomanip> #include <algorithm> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() using namespace std; typedef long long ll; ll linf = 1e15+1; inline void scoobydoobydoo(){ ios::sync_with_stdio(false); ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } ll s, n; const int MAXN = 2e3+1; vector<pair<ll, ll> > items[MAXN]; pair<ll, ll> elems[MAXN*MAXN]; // value, weight int counter = 0; ll mem[MAXN*30][MAXN]; ll dp(){ for (int j = elems[0].second; j <= s; j++){ mem[0][j] = elems[0].first; } for (int i = 1; i < counter; i++){ for (int j = elems[i].second; j <= s; j++){ mem[i][j] = max(max(mem[i-1][j], mem[i][j-1]), mem[i-1][j-elems[i].second]+elems[i].first); } } /*for (int i = 0; i < counter; i++){ cout << i << ": "; for (int j = 0; j <= s; j++){ cout << mem[i][j] << " "; } cout << endl; }*/ return mem[counter-1][s]; } int main(){ scoobydoobydoo(); cin >> s >> n; for (int i = 0; i < n; i++){ int v, w, k; cin >> v >> w >> k; if (w > s)continue; items[w].push_back({v, k}); } for (int i = 1; i < MAXN; i++)sort(rall(items[i])); for (int i = 1; i < MAXN; i++){ int how = 0; for (int j = 0; j < items[i].size() && how < s/i+1; j++){ int val = items[i][j].first; int k = items[i][j].second; for (int l = 0; l < k && how+l < s/i+1; l++){ elems[counter++] = {val, i}; } how += k; } } cout << dp() << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

knapsack.cpp: In function 'int main()':
knapsack.cpp:67:27: 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]
   67 |         for (int j = 0; j < items[i].size() && how < s/i+1; j++){
      |                         ~~^~~~~~~~~~~~~~~~~
#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...