Submission #1113831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113831		yazansh	Knapsack (NOI18_knapsack)	C++17	100 / 100	56 ms	7624 KiB

knapsack

#include <bits/stdc++.h> 
 
using namespace std; 
 
#define yon(x) cout<<((x)?"YES\n":"NO\n"); 
#define all(x) x.begin(),x.end() 
#define rall(x) x.rbegin(),x.rend() 
#define ff first 
#define ss second 
#define em emplace_back 
#define rep(i,j,k) for(int i=j;i<=k;i++) 
#define per(i,j,k) for(int i=k;i>=j;i--) 
#define forp(x,y,a) for(auto &[x,y]:(a)) 
typedef long long  ll; 
typedef pair<ll,ll> pll; 
typedef vector<ll> vl; 
typedef vector<pll> vpl; 
typedef vector<vl> vvl; 
typedef vector<vpl> vvpl; 
typedef vector<string> vs; 
typedef deque<ll> dl; 
const int mod=1e9+7; 
ll inf =1e18+1; 
const int M=1e6; 
const int N=1e3+1; 
const ll dx[]={1,0,-1,0},dy[]={0,1,0,-1}; 
void solve(){ 
ll n,s;
cin>>s>>n;
vl dp(s+1,-inf),a(n),b(n),c(n);
vvpl g(s+1);
rep(i,0,n-1){
  cin>>a[i]>>b[i]>>c[i];
if(c[i]){
    g[b[i]].em(a[i],c[i]);
}
}
rep(i,0,s)sort(all(g[i]));
vpl k;
rep(i,1,s){
    ll rem=s/i;
    //cout<<rem<<"\n";
    while(!g[i].empty()&&rem>0){
        ll val=g[i].back().ff,cnt=g[i].back().ss;
        g[i].pop_back();
rep(j,1,min(rem,cnt))k.em(val,i);
rem-=min(rem,cnt);
    }
}
dp[0]=0;
for(auto &[x,y]:k){
    //cout<<x<<" "<<y<<endl;
    per(j,y,s){
        dp[j]=max(dp[j-y]+x,dp[j]);
    }
}
cout<<*max_element(all(dp));
}
 
signed main() { 
    ios_base::sync_with_stdio(NULL); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    #ifdef Usaco 
    string f="herding"; 
    freopen((f+".in").c_str(),"r",stdin); 
    freopen((f+".out").c_str(),"w",stdout); 
    #endif 
    int t = 1; 
    //cin >> t; 
    while (t--) { 
        solve(); 
    //  if(t>0) 
      //cout<<endl; 
    } 
} 
/* 
*/

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