ulvis.paste.net

Paste Search Dynamic
Recent pastes
run
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. using namespace std;
  4. void run(){
  5.         ll n;
  6.         cin>>n;
  7.         ll c[n],w[n],M=0;
  8.         vector <ll> w1;
  9.         vector <ll> w2;
  10.         for(ll i=0;i<n;i++){
  11.                 cin>>w[i]>>c[i];
  12.                 M+=w[i];
  13.                 if(w[i]==1)w1.push_back(c[i]);
  14.                 else w2.push_back(c[i]);
  15.  
  16.         }
  17.         sort(w1.begin(),w1.end());
  18.         sort(w2.begin(),w2.end());
  19.         reverse(w1.begin(),w1.end());
  20.         reverse(w2.begin(),w2.end());
  21.                 ll dp[M+3][3]={0};
  22.         for(ll i=0;i<M+3;i++)
  23.         {       dp[i][0]=0;
  24.                 dp[i][1]=0;
  25.                 dp[i][2]=0;
  26.         }
  27.                 for(ll j=0;j<=M;j++){
  28.                         if(dp[j][1]<w1.size()&&(dp[j+1][0]<dp[j][0]+w1[dp[j][1]])){
  29.                                                                 dp[j+1][0]=dp[j][0]+w1[dp[j][1]];
  30.                                                                 dp[j+1][1]=dp[j][1]+1;dp[j+1][2]=dp[j][2];  }    
  31.                                                         //      if(j==0)cout<<dp[j+1][1]<<"A"<<endl;}
  32.                         else if(dp[j][1]<w1.size()&&(dp[j+1][0]==dp[j][0]+w1[dp[j][1]])){  
  33.                                                                 if(dp[j+1][1]>dp[j][1]+1) {
  34.                                                                                                         dp[j+1][1]=dp[j][1]+1;
  35.                                                                                                         dp[j+1][2]=dp[j][2];}  
  36.                                 //if(j==0)cout<<dp[j+1][1]<<"B"<<endl;
  37.                         }
  38.  
  39.                         if(dp[j][2]<w2.size()&&(dp[j+2][0]<dp[j][0]+w2[dp[j][2]])){dp[j+2][0]=dp[j][0]+w2[dp[j][2]];dp[j+2][2]=dp[j][2]+1;dp[j+2][1]=dp[j][1];}
  40.             else if(dp[j][2]<w2.size()&&(dp[j+2][0]==dp[j][0]+w2[dp[j][2]])){   if(dp[j+2][1]>dp[j][1]) {dp[j+2][1]=dp[j][1];     dp[j+2][2]=dp[j][2]+1;}}
  41.                 }
  42.                 ll mi=0;
  43.                 for(ll i=1;i<=M;i++){
  44.                         if(mi<dp[i][0])mi=dp[i][0];
  45.                         cout<<max(mi,dp[i][0])<<" ";
  46.                 }
  47.  
  48.  
  49.  
  50. }
  51. int main(){
  52.         ll t=1;
  53.         //cin>>t;
  54.         for(ll i=0;i<t;i++)run();
  55.  
  56. }
Parsed in 0.011 seconds