제출 #463581

#제출 시각아이디문제언어결과실행 시간메모리
463581Duy_eKnapsack (NOI18_knapsack)C++14
0 / 100
2 ms332 KiB
/*THINK GONNA FAIL ? IF U DIDNT FAIL THEN WHAT IS THE POINT OF LEARNING */ #include <bits/stdc++.h> #define ll long long #define pii pair<long long, long long> #define ull unsigned long long #define st first #define nd second #define lower_case_alphabet "abcdefghijklmnopqrstuvwxyz" #define upper_case_alphabet "ABCDEFGHIJKLMNOPQRSTUVWXYZ" #define file "test" using namespace std; const long long oo = 1e18; const long long N = 2e5 + 5; ll s, n, w[N], v[N], k[N], cnt, dp[N], A[N]; vector <pii> d[2004]; void decomposition(int x){ if (x == 0){ cnt = -1; return; } cnt = 0; int sum = 1; while (x > sum){ x -= sum; A[cnt++] = sum; sum <<= 1; } A[cnt] = x; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifndef ONLINE_JUDGE freopen(file".inp","r",stdin); freopen(file".out","w",stdout); #endif cin >> s >> n; for (int i = 1; i <= n; i ++){ cin >> v[i] >> w[i] >> k[i]; d[w[i]].push_back({v[i], k[i]}); } for (int i = 0; i <= s; i ++){ for (pii p: d[i]){ decomposition(p.nd); for (; cnt >= 0; cnt --){ ll W = A[cnt]*i, V = A[cnt]*p.st; for (int j = s; j >= W; j --) dp[j] = max(dp[j], dp[j-W] + V); } } } cout << dp[s]; return 0; } // sketch out every idea before see any solution, it helps alots. /** /\_/\ * (= ._.) * / >0 \>1 **/

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(file".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(file".out","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...