Submission #547842

#	Time	Username	Problem	Language	Result	Execution time	Memory
547842		topcoderme	Knapsack (NOI18_knapsack)	C++17	100 / 100	78 ms	4884 KiB

knapsack

#include <bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define F first
#define S second
#define all(v) (v).begin(),(v).end()
#define np next_permutation
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define vii vector<vi>
#define vb vector<bool>
#define pr pair<int,int>
#define vl vector<ll>
#define vs vector<string>
#define us unordered_map<int,int>
#define Mpq priority_queue<int>
#define mpq priority_queue<int,vi,greater<int>> 
#define eb emplace_back
#define pr pair<int,int>
#define prl pair<ll,ll>
#define vp vector<pr>
#define vpl vector<prl>
#define mkp make_pair
#define vi vector<int>
#define ld long double
#define vii vector<vi>
#define Max(a,b) a=max(a,b)
#define Min(a,b) a=min(a,b)
#define ull unsigned long long
#define prr pair<ll,int>
#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)
using namespace std;
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef  tree<int, null_type,less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
template<class T> using pqg = priority_queue<T,vector<T>,greater<T>>;
typedef long long ll;
#define NUMERIC_LIMIT std::numeric_limits<std::streamsize>::max()

double epsilon=1e-8;
const int N=int(1e5)+1;
const ll INF=ll(1e18);


class Time{
private:
   using clock_type = chrono::steady_clock;
   using second_type = chrono::duration<double,ratio<1>>;
   chrono::time_point<clock_type> m_init{clock_type::now()};
public:
   void reset(){
      m_init=clock_type::now();
   }
   double elapsed() const{
      return 
         chrono::duration_cast<second_type>(clock_type::now()-m_init).count();
   }
};

// int minp[N];
// void seive(){
//    vb s(N,1);
//    s[0]=s[1]=0;
//    for(int i{};i<N;++i)
//       minp[i]=i;
//    for(int i=2;i*i<N;++i){
//       if(!s[i]) continue;
//       for(int j=i*i;j<N;j+=i){
//          minp[j]=min(minp[j],i);
//          s[j]=1;
//       }
//    }
// }

// vp divs(int x){
//    vp d{};
//    while(x>1){
//       int p=minp[x];
//       int cnt{};
//       while(x>1 && x%p==0){
//          x/=p;
//          ++cnt;
//       }
//       d.eb(p,cnt);
//    }
//    return d;
//    if(d.empty()) return vi{1};
//    vi dv{};
//    for(int c=0;c<=d[0].S;++c){
//       dv.eb(pow(d[0].F,c));
//    }
//    for(int i=1;i<d.size();++i){
//       vi tmp{};
//       for(int c=0;c<=d[i].S;++c){
//          int val=pow(d[i].F,c);
//          for(int j=0;j<dv.size();++j)
//             tmp.eb(dv[j]*val);
//       }
//       dv=tmp;
//    }
//    return dv;
// }
// ll add(ll x,ll y){
//    x+=y;
//    while(x>=mod) x-=mod;
//    return x;
// }

ll s,n,v,w,c,ans;
ll dp[2001];
vector<prl> a[2001];
void solve(){
   cin >> s >> n;
   for(int i=0;i<n;++i){
      cin >> v >> w >> c;
      a[w].eb(v,c); 
   }
   for(int i=1;i<=s;++i){
      sort(all(a[i]),greater<prl>());
      int cnt{};
      for(int j=1;j<=(s/i);++j){
         if(cnt>=a[i].size()) break;
         for(int k=s;k>=i;--k){
            dp[k]=max(dp[k],dp[k-i]+a[i][cnt].F);
            ans=max(ans,dp[k]);
         } 
         --a[i][cnt].S;
         if(!a[i][cnt].S) ++cnt;
      }
   }
   cout << ans << '\n';
}

int main(){
   // #ifdef ONLINE_JUDGE
   //  freopen("input.txt", "r", stdin);
   //  freopen("output.txt", "w", stdout);
   // #endif
   
   ios_base::sync_with_stdio(0);  
   cin.tie(nullptr);

   int t{1};
   // cin >> t;
   for(int i=1;i<=t;i++){
      // cout << "Case #" << i << ": ";
      solve();  
   }     
}

Compilation message (stderr)

knapsack.cpp: In function 'void solve()':
knapsack.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |          if(cnt>=a[i].size()) break;
      |             ~~~^~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 27 / 27