제출 #463763

#제출 시각아이디문제언어결과실행 시간메모리
463763EntropyXKnapsack (NOI18_knapsack)C++17
49 / 100
181 ms15564 KiB
#include<bits/stdc++.h> #define _ ios_base::sync_with_stdio(0);cin.tie(0); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define iiordered_set tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update> using namespace std; //Bit Functions #define gcd __gcd #define lsb __builtin_ffs #define ldz __builtin_clz #define tlz __builtin_ctz #define stc __builtin_popcount #define prtb(n) cout << bitset<20>(n) << "\n"; //Debugging #define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); } #define what_is(x) cerr << #x << " is " << x << endl; void err(istream_iterator<string> it) {} template<typename T, typename... Args> void err(istream_iterator<string> it, T a, Args... args) { cerr << *it << " = " << a << endl; err(++it, args...); } //STL Declarations #define vi vector<int> #define vvi vector<vi> #define vl vector<long long int> #define vvl vector<vl> #define vb vector<bool> #define pii pair<int,int> #define fr first #define sc second #define u_s unordered_set #define ump unordered_map #define ins insert #define p_q(x) priority_queue<x> //STL Functions #define mt make_tuple #define eb emplace_back #define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define muq make_unique #define all(x) x.begin(),x.end() #define rot(vec,k) rotate(vec.begin(), vec.begin() + k, vec.end()); #define bs(vec,key) binary_search(all(vec), key) #define parti(vec,p) partition_point(all(vec), p) - vec.begin() #define srt(cnt) sort(all(cnt)) #define lb(cnt,x) lower_bound(all(cnt),x) #define ub(cnt,x) upper_bound(all(cnt),x) #define mxm(cnt) *max_element(all(cnt)) #define mnm(cnt) *min_element(all(cnt)) #define mxmptr(cnt) max_element(all(cnt)) #define mnmptr(cnt) min_element(all(cnt)) #define rev(cnt) reverse(all(cnt)) #define accum(cnt) accumulate(all(cnt),0) #define look(cnt) for(auto c:cnt) cout<<c<<" "; cout<<"\n"; #define pre(x,cont) find(all(cont),x)!=cont.end() #define pb push_back //Input Functions template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; } template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << t<<" "; return os << endl; } template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << v.first << " " << v.second ; } typedef long long int ll; ll mod = 10000000007; //Generalised Sum Function int sum() { return 0; } template<typename T, typename... Args> T sum(T a, Args... args) { return a + sum(args...); } vector<int> seive(int N){ vector<bool> visited(N+1,false); vi pr; for(int i=2;i<=N;i++){ if(!visited[i]){ int j = i; pr.pb(j); while(j<=N){visited[j] = true;j+=i;}}} return pr; } ll ceil(ll a,ll b){ if(b<0)a=-a,b=-b; if(a>=0)return (a+b-1)/b; return a/b; } long long bpow(long long a, long long b, long long m) { a %= m; long long res = 1; while (b > 0) { if (b & 1)res = res * a % m; a = a * a % m; b >>= 1; } return res; } ll inverse(ll a,ll m=mod) { return bpow(a,m-2,m); } vvl matmul(const vvl &a,const vvl &b,ll M=mod) { int n=a.size(),m=a[0].size(),l=b[0].size(); assert(m==b.size()); vvl c(n,vl(l,0)); rep(i,0,n) rep(j,0,l) rep(k,0,m) { c[i][j]=(c[i][j]+a[i][k]*b[k][j])%M; } return c; } vvl matpow(vvl a,ll p,ll M=mod) { assert(a.size()==a[0].size()); int n=a.size(); vvl res(n,vl(n,0)); rep(i,0,n) res[i][i]=1; while(p>0) { if(p&1) res=matmul(res,a,M); a=matmul(a,a,M); p>>=1; } return res; } const ll COMBINATION_SIZE = 300005; const ll MOD = 1e9+7; struct Combination { long long fac[COMBINATION_SIZE], inv[COMBINATION_SIZE]; bool built = 0; void build(){ assert(MOD >= COMBINATION_SIZE); fac[0] = 1; for(int i = 1; i < COMBINATION_SIZE; i++) { fac[i] = fac[i - 1] * i % MOD; } inv[COMBINATION_SIZE - 1] = inverse(fac[COMBINATION_SIZE - 1], MOD); for(int i = COMBINATION_SIZE - 2; i >= 0; i--) { inv[i] = inv[i + 1] * (i + 1) % MOD; } } long long C(int x, int y){ if(y < 0 || y > x) { return 0; } if(!built) { built = 1; build(); } return fac[x] * inv[y] % MOD * inv[x-y] % MOD; } } comb; void setIO(string s) { // the argument is the filename without the extension freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } ll s,n; void knap(vl &v, vl &w){ //Subtask 2 int n = v.size(); ll dp[n+1][s+1]; memset(dp,0,sizeof dp); ll ans = 0; rep(i,0,n+1){ rep(j,0,s+1){ if(i==0 || j == 0){ dp[i][j] = 0; } else{ dp[i][j] = dp[i-1][j]; if(j>=w[i-1]) dp[i][j] = max(dp[i][j],v[i-1] + dp[i-1][j-w[i-1]]); } if(i == n) ans = max(ans,dp[i][j]); } } cout << ans << "\n"; } int main(){ _ cin >> s >> n; vl v(n),w(n),k(n); bool s3 = true; bool s2 = true; rep(i,0,n) { cin >> v[i] >> w[i] >> k[i]; k[i] = min(k[i],s/w[i]); if(k[i]>1) s2 = false; if(k[i]>10) s3 = false; } if(n == 1){ // Subtask 1 ll req = min(s/w[0],k[0]); cout << req*v[0] << "\n"; } else if(n <=100 && s2){ knap(v,w); } else if(n<=100 && s3){ //Subtask 3 vl v1,w1; rep(i,0,n){ rep(j,0,k[i]) { v1.pb(v[i]); w1.pb(w[i]); } } v = v1;w = w1; knap(v,w); } else if(n<=100){ //Subtask 4 int n = v.size(); ll dp[n+1][s+1]; memset(dp,0,sizeof dp); ll ans = 0; rep(i,0,n+1){ rep(j,0,s+1){ if(i==0 || j == 0){ dp[i][j] = 0; } else{ dp[i][j] = dp[i-1][j]; rep(kk,1,k[i]+1){ if(j>=kk*w[i-1]) { dp[i][j] = max(dp[i][j], v[i - 1] + dp[i - 1][j - kk * w[i - 1]]); } else{ break; } } } if(i == n) ans = max(ans,dp[i][j]); } } } else{ //Subtask 5 cout << "-1\n"; } return 0; }

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

In file included from /usr/include/c++/10/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp:45,
                 from /usr/include/c++/10/ext/pb_ds/detail/container_base_dispatch.hpp:90,
                 from /usr/include/c++/10/ext/pb_ds/assoc_container.hpp:48,
                 from knapsack.cpp:4:
knapsack.cpp: In function 'std::vector<std::vector<long long int> > matmul(const std::vector<std::vector<long long int> >&, const std::vector<std::vector<long long int> >&, ll)':
knapsack.cpp:111:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     assert(m==b.size());
      |            ~^~~~~~~~~~
knapsack.cpp: In function 'void setIO(std::string)':
knapsack.cpp:166:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |     freopen((s+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:167:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     freopen((s+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...