Submission #574832

#TimeUsernameProblemLanguageResultExecution timeMemory
574832codebuster_10Knapsack (NOI18_knapsack)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #define int int64_t //be careful about this using namespace std; #define vt vector #define ar array #define pr pair #define f first #define s second #define pb push_back #define eb emplace_back #define fr(i,a,b) for(int i = a; i < b; ++i) #define rf(i,a,b) for(int i = b-1; i >= a; --i) #define all(x) x.begin(),x.end() #define mem(a,b) memset(a,b,sizeof(a)) namespace IN{ template<class T> void re(vector<T> &A); template<class S,class T> void re(pair<S,T> &A); template<class T,size_t N> void re(array<T,N> &A); template<class T> void re(T& x){ cin >> x;} template<class H, class... T> void re(H& h, T&... t){ re(h); re(t...);} template<class T> void re(vector<T> &A){ for(auto& x : A) re(x);} template<class S,class T> void re(pair<S,T> &A){ re(A.first); re(A.second);} template<class T,size_t N> void re(array<T,N> &A){ for(int i = 0; i < N; ++i) re(A[i]);} } namespace OUT{ template<class T> void __p(const T& a){ cout<<a; } template<class T, class F> void __p(const pair<T, F>& a){ cout<<"{"; __p(a.first); cout<<","; __p(a.second); cout<<"}\n"; } template<class T, size_t N> void __p(const array<T,N>& a){ cout<<"{"; for(int i=0;i<N;++i)__p(a[i]),cout<<",}\n"[i+1==N]; } template<class T> void __p(const vector<T>& a){ cout<<"{";for(auto it=a.begin();it<a.end();it++)__p(*it),cout<<",}\n"[it+1==a.end()]; } template<class T, class ...Arg> void __p(T a1, Arg ...a){__p(a1); __p(a...); } template<class Arg1> void __f(const char *s, Arg1 &&arg1){ cout<<s<<" : "; __p(arg1); cout<<endl; } template<class Arg1, class ... Args> void __f(const char *ss, Arg1 &&arg1, Args &&... args){ int b=0,i=0; do{ if(ss[i]=='(') b++; if(ss[i]==')') b--; i++;}while(!(ss[i]==','&&b==0)); const char *comma=ss+i; cout.write(ss,comma-ss)<<" : ";__p(arg1);cout<<" | ";__f(comma+1,args...);} #define trace(...) cout<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__) } namespace FUNC{ void IO(string s = ""){ ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.precision(20); cout << fixed; if(!s.empty()){ freopen((s+".in").c_str(),"r",stdin); freopen((s+".out").c_str(),"w",stdout); } } const auto start_time = chrono::high_resolution_clock::now(); void output_run_time(){ // will work for ac,cc&&cf. #ifndef ONLINE_JUDGE auto end_time = chrono::high_resolution_clock::now(); chrono::duration<double> diff = end_time-start_time; cout << "\n\n\nTime Taken : " << diff.count(); #endif } template<class T> bool ckmin(T& a, const T& b){ return b < a ? a = b, true : false; } template<class T> bool ckmax(T& a, const T& b){ return a < b ? a = b, true : false; } mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); int my_rand(int L, int R){ return uniform_int_distribution<int>(L,R)(rng); } template<class T> int sz(const T& x){ return int(x.size()); } template<class T> int lb(const vector<T>& vec,const T& val){ return int(lower_bound(vec.begin(), vec.end(),val) - vec.begin()); } template<class T> int ub(const vector<T>& vec,const T& val){ return int(upper_bound(vec.begin(), vec.end(),val) - vec.begin()); } constexpr int dx[4] = {1,0,-1,0}; constexpr int dy[4] = {0,1,0,-1}; constexpr char dr[4] = {'D','R','U','L'}; constexpr long long INFLL1 = 1e16, INFLL2 = 9e18; constexpr int INF = 2e9; template<class T> vector<T> V(int n,T val){ return vector<T> (n,val); } template<class T> vector<vector<T>> V(int n,int m,T val){ return vector<vector<T>> (n,vector<T> (m,val)); } template<class T> vector<vector<vector<T>>> V(int n,int m,int k,T val){ return vector<vector<vector<T>>> (n,vector<vector<T>> (m,vector<T> (k,val))); } } using namespace IN; using namespace OUT; using namespace FUNC; template<const unsigned &MOD> struct _m_uint { unsigned val; _m_uint(int64_t v = 0){ if(v < 0) v = v % MOD + MOD; if(v >= MOD) v %= MOD; val = unsigned(v); } _m_uint(uint64_t v){ if(v >= MOD) v %= MOD; val = unsigned(v); } _m_uint(int v) : _m_uint(int64_t(v)) {} _m_uint(unsigned v) : _m_uint(uint64_t(v)) {} explicit operator unsigned() const { return val; } explicit operator int64_t() const { return val; } explicit operator uint64_t() const { return val; } explicit operator double() const { return val; } explicit operator long double() const { return val; } _m_uint& operator+=(const _m_uint &other){ val = val < MOD - other.val ? val + other.val : val - (MOD - other.val); return *this; } _m_uint& operator-=(const _m_uint &other){ val = val < other.val ? val + (MOD - other.val) : val - other.val; return *this; } static unsigned fast_mod(uint64_t x, unsigned m = MOD){ return unsigned(x % m); } _m_uint& operator*=(const _m_uint &other){ val = fast_mod(uint64_t(val) * other.val); return *this; } _m_uint& operator/=(const _m_uint &other){ return *this *= other.inv(); } friend _m_uint operator+(const _m_uint &a, const _m_uint &b){ return _m_uint(a) += b; } friend _m_uint operator-(const _m_uint &a, const _m_uint &b){ return _m_uint(a) -= b; } friend _m_uint operator*(const _m_uint &a, const _m_uint &b){ return _m_uint(a) *= b; } friend _m_uint operator/(const _m_uint &a, const _m_uint &b){ return _m_uint(a) /= b; } _m_uint& operator++(){ val = val == MOD - 1 ? 0 : val + 1; return *this; } _m_uint& operator--(){ val = val == 0 ? MOD - 1 : val - 1; return *this; } _m_uint operator++(int){ _m_uint before = *this; ++*this; return before; } _m_uint operator--(int){ _m_uint before = *this; --*this; return before; } _m_uint operator-() const { return val == 0 ? 0 : MOD - val; } friend bool operator==(const _m_uint &a, const _m_uint &b) { return a.val == b.val; } friend bool operator!=(const _m_uint &a, const _m_uint &b) { return a.val != b.val; } friend bool operator<(const _m_uint &a, const _m_uint &b) { return a.val < b.val; } friend bool operator>(const _m_uint &a, const _m_uint &b) { return a.val > b.val; } friend bool operator<=(const _m_uint &a, const _m_uint &b) { return a.val <= b.val; } friend bool operator>=(const _m_uint &a, const _m_uint &b) { return a.val >= b.val; } static const int SAVE_INV = int(1e6) + 5; static _m_uint save_inv[SAVE_INV]; static void prepare_inv(){ // Make sure MOD is prime, which is necessary for the inverse algorithm below. for(int64_t p = 2; p * p <= MOD; p += p % 2 + 1){ assert(MOD % p != 0); } save_inv[0] = 0; save_inv[1] = 1; for (int i = 2; i < SAVE_INV; i++){ save_inv[i] = save_inv[MOD % i] * (MOD - MOD / i); } } _m_uint inv() const { if(save_inv[1] == 0) prepare_inv(); if(val < SAVE_INV) return save_inv[val]; _m_uint product = 1; unsigned v = val; while(v >= SAVE_INV){ product *= MOD - MOD / v; v = MOD % v; } return product * save_inv[v]; } _m_uint pow(int64_t p) const { if(p < 0) return inv().pow(-p); _m_uint a = *this, result = 1; while(p > 0){ if(p & 1) result *= a; p >>= 1; if(p > 0) a *= a; } return result; } friend ostream& operator<<(ostream &os, const _m_uint &m){ return os << m.val; } }; template<const unsigned &MOD> _m_uint<MOD> _m_uint<MOD>::save_inv[_m_uint<MOD>::SAVE_INV]; const unsigned MOD = unsigned(1e9) + 7; using mint = _m_uint<MOD>; signed main(){ IO(); int S,N; re(S,N); vt<pr<int,int>> W[S+1]; fr(i,0,N){ int v,w,k; re(v,w,k); W[w].pb({v,k}); } vt<int> dp(S+1,0); fr(w,1,S+1){ sort(all(W[w])); auto prv_dp = dp; for(int i = 1, tot = 0; i*w <= S && !W[w].empty(); i++){ tot += W[w].back().f; if((--W[w].back().s) == 0) W[w].pop_back(); fr(j,0,S+1){ if(j+i*w <= S) ckmax(dp[j+i*w],tot+prv_dp[j]); } } } int ans = 0; fr(i,1,S+1) ckmax(ans,dp[i]); cout << ans; output_run_time(); return 0; }

Compilation message (stderr)

knapsack.cpp:155:3: error: '_m_uint<MOD>::_m_uint(int64_t)' cannot be overloaded with '_m_uint<MOD>::_m_uint(int64_t)'
  155 |   _m_uint(int v) : _m_uint(int64_t(v)) {}
      |   ^~~~~~~
knapsack.cpp:144:3: note: previous declaration '_m_uint<MOD>::_m_uint(int64_t)'
  144 |   _m_uint(int64_t v = 0){
      |   ^~~~~~~
knapsack.cpp: In function 'void FUNC::IO(std::string)':
knapsack.cpp:68:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |       freopen((s+".in").c_str(),"r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
knapsack.cpp:69:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |       freopen((s+".out").c_str(),"w",stdout);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~