Submission #1042297

#TimeUsernameProblemLanguageResultExecution timeMemory
1042297devvikram34Knapsack (NOI18_knapsack)C++17
100 / 100
74 ms8220 KiB
#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 = 1000000007, inf = (ll)2e16, N = (ll)1e6; void __( ) { int s, n; in(s, n); vector<vector<int>> a(n, vector<int>(3)); for ( auto &&i : a ) { in(i[0], i[1], i[2]); i[2] = min(i[2], s / i[1]); } sort(a.begin( ), a.end( ), [&](vector<int> &l, vector<int> &r) { return (l[1] < r[1]) ? true : (l[1] == r[1]) ? l[0] > r[0] : false; }); // db(a); int d = 0, p = 0; vector<pair<int, vector<int>>> v; for ( auto &&i : a ) { if ( p != i[1] ) { d = 0; v.push_back({i[1], {}}); } for ( auto j = 0; d + i[1] <= s and j < i[2]; j += 1 ) { d += i[1]; v.back( ).second.push_back(i[0]); } p = i[1]; } a.clear( ); // db(v); n = v.size( ); vector<vector<int>> dp(2, vector<int>(s + 1, -inf)); dp[0][0] = 0; for ( auto i = 0; i < n; i += 1 ) { for ( auto j = 0; j <= s; j += 1 ) { int val = 0; dp[1][j] = dp[0][j]; for ( auto k = 0; (k + 1) * v[i].first <= j and k < v[i].second.size( ); k += 1 ) { val += v[i].second[k]; dp[1][j] = max(dp[1][j], dp[0][j - (k + 1) * v[i].first] + val); } } dp[0] = dp[1]; } out(*max_element(all(dp[0]))); } signed main( ) { cin.tie(0)->sync_with_stdio(0); __( ); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'void __()':
knapsack.cpp:47:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |          for ( auto k = 0; (k + 1) * v[i].first <= j and k < v[i].second.size( ); k += 1 ) {
      |                                                          ~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...