이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
*
* ^v^
*
*/
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <iomanip>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <climits>
#include <cstdlib>
#include <chrono>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define iamtefu ios_base::sync_with_stdio(false); cin.tie(0);
#define ll long long int
#define ld long double
#define fl(i,a,n) for (int i(a); i<n; i++)
#define rfl(i,a,n) for (int i(n-1); i>=a; i--)
#define print(a) for (auto x:a){cout<<x<<" ";} cout<<"\n";
#define tt int tt; cin>>tt; for(;tt--;)
template <typename T1, typename T2>
decltype(auto) max(T1 a, T2 b){return (a>b?a:b);}
template <typename T1, typename T2>
decltype(auto) min(T1 a, T2 b){return (a<b?a:b);}
int gcd(int a, int b){
if (b==0){
return a;
}
return gcd(b, a%b);
}
int pw(int a, int b, int m){
int res=1;
a%=m;
while (b){
if (b&1){
res=(res*a)%m;
}
a=(a*a)%m;
b>>=1;
}
return res;
}
void scn(){
int n, s; cin>>s>>n;
vector <vector <vector <int>>> huh(s+1);
fl(i,0,n){
int v, w, k; cin>>v>>w>>k;
huh[w].push_back({v, k});
}
for (auto &x:huh){
sort(x.rbegin(), x.rend());
}
vector <vector <int>> eheh;
fl(i,1,s+1){
int sz = (s+i-1)/i;
for (auto x:huh[i]){
if (sz==0){
break;
}
int jk = min(sz, x[1]);
while (jk){
jk--;
eheh.push_back({x[0], i});
}
sz-=(min(sz, x[1]));
}
}
huh.clear();
vector <int> dp(s+1);
dp[0]=1;
fl(i,1,eheh.size()+1){
rfl(j,0,s+1){
if (dp[j-eheh[i-1][1]]){
dp[j]=max(dp[j], dp[j-eheh[i-1][1]]+eheh[i-1][0]);
}
}
}
cout<<dp[s]-1<<'\n';
}
int main(){
iamtefu;
#if defined(airths)
auto t1=chrono::high_resolution_clock::now();
freopen("in", "r", stdin);
freopen("out", "w", stdout);
#else
//
#endif
// tt
{
scn();
}
#if defined(airths)
auto t2=chrono::high_resolution_clock::now();
ld ti=chrono::duration_cast<chrono::nanoseconds>(t2-t1).count();
ti*=1e-6;
cerr<<"Time: "<<setprecision(12)<<ti;
cerr<<"ms\n";
#endif
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In function 'void scn()':
knapsack.cpp:26:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | #define fl(i,a,n) for (int i(a); i<n; i++)
......
80 | fl(i,1,eheh.size()+1){
| ~~~~~~~~~~~~~~~~~
knapsack.cpp:80:2: note: in expansion of macro 'fl'
80 | fl(i,1,eheh.size()+1){
| ^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |