제출 #677274

#제출 시각아이디문제언어결과실행 시간메모리
677274airthsKnapsack (NOI18_knapsack)C++17
73 / 100
154 ms262144 KiB
/* * * ^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<ll, null_type, less<ll>, 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 (ll i(a); i<n; i++) #define rfl(i,a,n) for (ll 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);} ll gcd(ll a, ll b){ if (b==0){ return a; } return gcd(b, a%b); } ll pw(ll a, ll b, ll m){ ll res=1; a%=m; while (b){ if (b&1){ res=(res*a)%m; } a=(a*a)%m; b>>=1; } return res; } void scn(){ ll n, s; cin>>s>>n; vector <vector <vector <ll>>> huh(s+1); fl(i,0,n){ ll v, w, k; cin>>v>>w>>k; huh[w].push_back({v, k}); } for (auto &x:huh){ sort(x.rbegin(), x.rend()); } vector <vector <ll>> eheh; fl(i,1,s+1){ ll sz = (s+i-1)/i; for (auto x:huh[i]){ ll jk = min(sz, x[1]); while (jk){ jk--; eheh.push_back({x[0], i}); } sz-=(min(sz, x[1])); } } huh.clear(); vector <vector<ll>> dp(eheh.size()+1, vector <ll>(s+1)); fl(i,1,eheh.size()+1){ fl(j,0,s+1){ dp[i][j]=dp[i-1][j]; if (j>=eheh[i-1][1]){ dp[i][j]=max(dp[i][j], dp[i-1][j-eheh[i-1][1]]+eheh[i-1][0]); } } } cout<<dp[eheh.size()][s]<<'\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:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 | #define fl(i,a,n) for (ll i(a); i<n; i++)
......
   76 |  fl(i,1,eheh.size()+1){
      |     ~~~~~~~~~~~~~~~~~             
knapsack.cpp:76:2: note: in expansion of macro 'fl'
   76 |  fl(i,1,eheh.size()+1){
      |  ^~
#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...