제출 #540569

#제출 시각아이디문제언어결과실행 시간메모리
540569ac2huKnapsack (NOI18_knapsack)C++14
73 / 100
1095 ms102304 KiB
#include <bits/stdc++.h> #ifdef DEBUG #include "../templates/debug.h" #else #define deb(x...) #endif using namespace std; #define int long long signed main() { iostream::sync_with_stdio(false); cin.tie(nullptr);cout.tie(nullptr); int s,n;cin >> s >> n; int ll = ceil(log2(s)); vector<array<int,3>> iitems(n); vector<array<int,3>> items; for(int i = 0;i<n;i++){ for(int j = 0;j<3;j++)cin >> iitems[i][j]; iitems[i][2] = min(iitems[i][2], s); while(iitems[i][2] > 0){ int lg = log2(iitems[i][2]); iitems[i][2] -= (1 << lg); deb(i, lg); items.push_back({iitems[i][0], iitems[i][1], 1}); for(int mask =0;mask<lg;mask++){ items.push_back({iitems[i][0]*(1 << mask), iitems[i][1]*(1 << mask), (1 << mask)}); } } } deb(items); vector<int> old((int)2e3 + 10), ne((int)2e3 + 10); for(int i = 0;i<items.size();i++){ swap(old, ne); for(int j = 1;j<=s;j++){ ne[j] = max(old[j], ne[j - 1]); if(j >= items[i][1]) ne[j] = max(ne[j], old[j - items[i][1]] + items[i][0]); } } cout << ne[s] << "\n"; }

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

knapsack.cpp: In function 'int main()':
knapsack.cpp:31:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         for(int i = 0;i<items.size();i++){
      |                       ~^~~~~~~~~~~~~
knapsack.cpp:13:13: warning: unused variable 'll' [-Wunused-variable]
   13 |         int ll = ceil(log2(s));
      |             ^~
#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...