제출 #583800

#제출 시각아이디문제언어결과실행 시간메모리
583800jack715Knapsack (NOI18_knapsack)C++14
100 / 100
53 ms1680 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define pp pop_back #define mp make_pair #define bb back #define ff first #define ss second // #define int long long using namespace std; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("tmp.in", "r", stdin); // freopen("tmp.out", "w", stdout); int s, n, a, b, c; cin >> s >> n; vector<pair<int, int> > nums[2005]; vector<int> op[2005]; for (int i = 0; i < n; i++) { cin >> a >> b >> c; nums[b].pb({a, c}); } int dp[2005], now; for (int i = 1; i <= s; i++) { sort(nums[i].rbegin(), nums[i].rend()); now = 0; op[i].resize(s/i); for (int j = 0; j < nums[i].size() && now < s/i; j++) { for (int k = 0; k < nums[i][j].ss && now < s/i; k++) { op[i][now] = nums[i][j].ff, now++; } } } memset(dp, -1, sizeof(dp)); dp[0] = 0; for (int i = 1; i <= s; i++) { for(int j = s; j >= 0; j--) { now = 0; for(int x = 1; x <= s/i; x++) { now += op[i][x-1]; if(j - x * i < 0) break; dp[j] = max(dp[j], dp[j - x * i] + now); } } } int ans = 0; for(int i = 0; i <= s; i ++) { ans = max(ans, dp[i]); } cout << ans << '\n'; return 0; } /* stuff you should look for * int overflow, array bounds * special cases (n=1?) * do smth instead of nothing and stay organized * WRITE STUFF DOWN * DON'T GET STUCK ON ONE APPROACH */

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:33:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         for (int j = 0; j < nums[i].size() && now < s/i; 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...