제출 #705994

#제출 시각아이디문제언어결과실행 시간메모리
705994lukameladzeKnapsack (NOI18_knapsack)C++14
73 / 100
1077 ms18076 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define pii pair <long long, long long> #define pb push_back const int N = 1e6 + 5; int t,n,w[N],s; long long dp[N],v[N],k[N]; main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>s>>n; vector <pii> vec; vec.pb({0, 0}); for (int i = 1; i <= n; i++) { cin>>v[i]>>w[i]>>k[i]; for (int j = 0; j <= 12; j++) { if (k[i] >= (1<<j)) { long long x = (1<<j); k[i] -= x; if (x * w[i] <= s) vec.pb({x * v[i], x * w[i]}); } } if (k[i] <= s && k[i] && w[i] * k[i] <= s) vec.pb({k[i] * v[i], k[i] * w[i]}); } long long ans = 0; for (int i = 1; i < vec.size(); i++) { for (int j = s; j >= vec[i].s; j--) { dp[j] = max(dp[j], dp[j - vec[i].s] + vec[i].f); ans = max(ans, dp[j]); } } cout<<ans<<"\n"; }

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

knapsack.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main() {
      | ^~~~
knapsack.cpp: In function 'int main()':
knapsack.cpp:28:23: 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]
   28 |     for (int i = 1; i < vec.size(); i++) {
      |                     ~~^~~~~~~~~~~~
#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...