제출 #993120

#제출 시각아이디문제언어결과실행 시간메모리
993120cpdreamerKnapsack (NOI18_knapsack)C++17
12 / 100
1 ms604 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <utility> using namespace __gnu_pbds; using namespace std; typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set; const int max_n=INT_MAX; typedef long long ll; #define LLM LONG_LONG_MAX #define pb push_back #define F first #define L length() #define all(v) v.begin(),v.end() #define P pair #define V vector #define S second const long long MOD = 1000000007; // 1e9 + 7 void file(){ freopen("input.txt.txt","r",stdin); freopen("output.txt.txt","w",stdout); } void setio(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } bool is_sorted(int A[],int n) { for (int i = 0; i < n - 1; i++) { if (A[i] > A[i + 1]) return false; } return true; } void solve() { int W, n; cin >> W >> n; int v[n], k[n], w[n]; V<V<P<ll, ll>>> vp(W + 1); V<V<P<ll, ll>>> pref(W + 1); for (int i = 0; i < n; i++) { cin >> v[i] >> w[i] >> k[i]; vp[w[i]].pb({v[i], k[i]}); } ll dp[W + 1]; bool made[W + 1]; memset(dp, -1, sizeof(dp)); memset(made, false, sizeof(dp)); dp[0] = 0; made[0] = true; for (int i = 1; i <= W; i++) { sort(all(vp[i])); reverse(all(vp[i])); } for (int i = 1; i <= W; i++) { if (!vp[i].empty()) { pref[i].pb({vp[i][0].F*vp[i][0].S,vp[i][0].S}); for (int j = 1; j < vp[i].size(); j++) { pref[i].pb({vp[i][j].F*vp[i][j].S + pref[i][j - 1].F, vp[i][j].S + pref[i][j - 1].S}); } } } for (int i = 1; i <= W; i++) { if (!vp[i].empty()) { for (int j = W; j >= i; j--) { int weight = j; int l = 0, r = (int)pref[i].size() - 1; int ans = -1; while (l <= r) { int m = l + (r - l) / 2; if (pref[i][m].S * i >= j) { ans = m; r = m - 1; } else l = m + 1; } if (ans == -1) ans = (int) vp[i].size() - 1; int a = 0; ll value=0; if (ans > 0) { a = (int) pref[i][ans - 1].S * i; value = (int) pref[i][ans - 1].F; } weight -= a; int add = min((weight / i),(int)vp[i][ans].S); a += add*i; value+=(int) vp[i][ans].F * add; if (made[j - a]) { made[j] = true; dp[j] = max(dp[j], dp[j - a] + value); } } } } cout << *max_element(dp, dp + W + 1) << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); //file(); solve(); return 0; }

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

knapsack.cpp: In function 'void solve()':
knapsack.cpp:59:31: 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]
   59 |             for (int j = 1; j < vp[i].size(); j++) {
      |                             ~~^~~~~~~~~~~~~~
knapsack.cpp: In function 'void file()':
knapsack.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen("input.txt.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen("output.txt.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void setio(std::string)':
knapsack.cpp:26:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:27:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...