Submission #1042049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042049		devvikram34	Knapsack (NOI18_knapsack)	C++17	29 / 100	350 ms	1084 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
// clang-format off
template <class __T1, class __T2>ostream &operator<<( ostream &__X1, const pair<__T1, __T2> &__P1 );template <typename _T1, typename = enable_if_t<!is_same_v<_T1, string> && !is_void_v<typename _T1::value_type>>>ostream &operator<<( ostream &__X1, const _T1 &__V1 ) { if ( &__X1 == &cerr )__X1 << "[ ";bool _1FL = false, _1Bg = true; for ( auto &_G1 : __V1 ) {_1FL = is_same_v<decay_t<decltype( _G1 )>, char> or is_same_v<decay_t<decltype( _G1 )>, long long> or is_same_v<decay_t<decltype( _G1 )>, int>;( !_1FL or _1Bg ) ? __X1 << _G1 : __X1 << ( ( &__X1 == &cerr ) ? ", " : " " ) << _G1; _1Bg = false; } if ( &__X1 == &cerr ) return __X1 << " ]..";   return _1FL ? __X1 << '\n' : __X1;}template <class __T1, class __T2>ostream &operator<<( ostream &__X1, const pair<__T1, __T2> &__P1 ) { if ( &__X1 == &cerr ) return __X1 << "<" << __P1.first << ", " << __P1.second << "> "; return __X1 << __P1.first << ' ' << __P1.second;}template <class... Ts>void __prnt( const Ts &..._1AG ) { ( ( cerr << _1AG << " __ " ), ... );   cerr << '\n';}
#define db(...) (cerr << " (:> " << #__VA_ARGS__ << " |= ", __prnt(__VA_ARGS__))
template <class __2T>void __scan( __2T &_2Ti ) { cin >> _2Ti;}template <class __2T, class S>void __scan( pair<__2T, S> &__P2 ) {__scan( __P2.first ), __scan( __P2.second );}template <class __2T>void __scan( vector<__2T> &_2Ti ) {   for ( auto &i : _2Ti )__scan( i );}template <typename... _1VL>void in( _1VL &..._4W ) {( __scan( _4W ), ... );}template <typename _1T>void out( const _1T &_1Ar ) {if constexpr ( is_same_v<_1T, char> )( _1Ar == '\n' ) ? cout << _1Ar << "" : cout << _1Ar << " ";else if constexpr ( is_same_v<_1T, int> or is_same_v<_1T, long long> or is_same_v<_1T, string> )cout << _1Ar << " "; else cout << _1Ar << "";}template <typename... Args>void out( const Args &...args ) { ( out( args ), ... );}
// clang-format on
#define all(vls) vls.begin( ), vls.end( )
#define int long long
#define ll long long
const ll md = 1e9 + 7, inf = (ll)2e16, N = (ll)1e2;

void __( ) {
   int s, n;
   in(s, n);
   vector<int> v(n), w(n), k(n), f(s + 1);
   for ( auto i = 0; i < n; i += 1 ) {
      in(v[i], w[i], k[i]);
   }
   vector<vector<int>> dp(2, vector<int>(s + 1, -inf)), m(3, vector<int>(2));
   dp[0][0] = 0;
   for ( auto i = 0; i < n; i += 1 ) {
      for ( auto j = 0; j <= s; j += 1 ) {
         dp[1][j] = dp[0][j];
         if ( j >= w[i] ) {
            m = {{dp[1][j], 0}, {dp[0][j - w[i]] + v[i], 1}, {dp[1][j - w[i]] + v[i], 2}};
            sort(m.rbegin( ), m.rend( ));
            if ( m[0][1] == 2 ) {
               if ( f[j - w[i]] < k[i] ) {
                  dp[1][j] = m[0][0];
                  f[j] = f[j - w[i]] + 1;
               } else {
                  dp[1][j] = m[1][0];
                  f[j] += (m[1][1] ? 1 : 0);
               }
            }
            if ( m[0][1] == 1 ) {
               dp[1][j] = m[0][0];
               f[j]++;
            }
         }
      }
      // db(dp);
      db(i, f);
      dp[0] = dp[1];
      fill(all(f), 0);
   }
   out(*max_element(all(dp[0])));
   // db(dp[0]);
}

signed main( ) {
   cin.tie(0)->sync_with_stdio(0);
   __( );
   return 0;
}

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