Submission #471824

#TimeUsernameProblemLanguageResultExecution timeMemory
471824CodeChamp_SSKnapsack (NOI18_knapsack)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define ff first #define ss second #define pb push_back #define eb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define setbits(x) __builtin_popcountll(x) #define zrobits(x) __builtin_ctzll(x) #define sz(v) (int)v.size() #define ps(y) cout << fixed << setprecision(y) #define ms(arr, v) memset(arr, v, sizeof(arr)) #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define trav(x, v) for(auto &x: v) #define w(t) int t; cin >> t; while(t--) #define rep(i, a, b) for(int i = a; i <= b; i++) #define rrep(i, a, b) for(int i = a; i >= b; i--) #define rep0(i, n) rep(i, 0, n - 1) #define rrep0(i, n) rrep(i, n - 1, 0) #define rep1(i, n) rep(i, 1, n) #define rrep1(i, n) rrep(i, n, 1) #define inp(arr, n) rep0(i, n) cin >> arr[i]; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> pii; typedef vector<ll> vi; typedef vector<vi> vvi; typedef vector<pii> vp; typedef vector<bool> vb; typedef vector<string> vs; typedef map<ll, ll> mii; typedef map<char, ll> mci; typedef priority_queue<ll> pq_mx; typedef priority_queue<ll, vi, greater<>> pq_mn; typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds; /* * find_by_order(i) -> returns an iterator to the element at ith position (0 based) * order_of_key(i) -> returns the position of element i (0 based) */ const int N = 1e5 + 5, M = 2e3 + 5; const int mod = 1e9 + 7; //const int mod = 998244353; const ll inf = 1e18; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fio() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); } int n, s, Vi[N], wi[N], ki[N]; vi dp; ll f(int i, int j) { if (i == n) return 0; if (dp[i][j] != -1) return dp[i][j]; ll ans = 0; for (ll x = 0; x <= ki[i] and j + x * wi[i] <= s; x++) ans = max(ans, x * Vi[i] + f(i + 1, j + x * wi[i])); return dp[i][j] = ans; } int main() { fio(); cin >> s >> n; rep0(x, n) cin >> Vi[x] >> wi[x] >> ki[x]; dp.assign(n, vi(s + 1, -1)); cout << f(0, 0); return 0; }

Compilation message (stderr)

knapsack.cpp: In function 'll f(int, int)':
knapsack.cpp:67:14: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type {aka long long int}[int]' for array subscript
   67 |     if (dp[i][j] != -1) return dp[i][j];
      |              ^
knapsack.cpp:67:37: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type {aka long long int}[int]' for array subscript
   67 |     if (dp[i][j] != -1) return dp[i][j];
      |                                     ^
knapsack.cpp:70:17: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type {aka long long int}[int]' for array subscript
   70 |     return dp[i][j] = ans;
      |                 ^
knapsack.cpp: In function 'int main()':
knapsack.cpp:79:31: error: no matching function for call to 'std::vector<long long int>::assign(int&, vi)'
   79 |     dp.assign(n, vi(s + 1, -1));
      |                               ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from knapsack.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:749:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = long long int; _Alloc = std::allocator<long long int>; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = long long int]'
  749 |       assign(size_type __n, const value_type& __val)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:749:47: note:   no known conversion for argument 2 from 'vi' {aka 'std::vector<long long int>'} to 'const value_type&' {aka 'const long long int&'}
  749 |       assign(size_type __n, const value_type& __val)
      |                             ~~~~~~~~~~~~~~~~~~^~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note: candidate: 'template<class _InputIterator, class> void std::vector<_Tp, _Alloc>::assign(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = long long int; _Alloc = std::allocator<long long int>]'
  768 |  assign(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:768:2: note:   template argument deduction/substitution failed:
knapsack.cpp:79:31: note:   deduced conflicting types for parameter '_InputIterator' ('int' and 'std::vector<long long int>')
   79 |     dp.assign(n, vi(s + 1, -1));
      |                               ^
In file included from /usr/include/c++/10/vector:67,
                 from /usr/include/c++/10/functional:62,
                 from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/10/algorithm:74,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from knapsack.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:794:7: note: candidate: 'void std::vector<_Tp, _Alloc>::assign(std::initializer_list<_Tp>) [with _Tp = long long int; _Alloc = std::allocator<long long int>]'
  794 |       assign(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:794:7: note:   candidate expects 1 argument, 2 provided