제출 #706004

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

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

knapsack.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main() {
      | ^~~~
#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...