Submission #780449

#	Time	Username	Problem	Language	Result	Execution time	Memory
780449		myde	Knapsack (NOI18_knapsack)	C++17	Compilation error	0 ms	0 KiB

knapsack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define ff first
#define ss second
#define inp_v(vec)    \
  for (auto &i : vec) \
    cin >> i;
#define prt_v(vec)   \
  for (auto i : vec) \
    cout << i << endl;
#define MS(x) memset(x, 0, sizeof(x))
#define gcd(a, b) __gcd(a, b);
#define lcm(a, b) (a * (b / gcd(a, b)))
#define lb lower_bound
#define ub upper_bound
bool chmin(int &a, int b)
{
  return b < a ? a = b, true : false;
}
bool chmax(int &a, int b) { return b > a ? a = b, true : false; }
bool comp(const pair<int, int> &a, const pair<int, int> &b)
{
  return a.first > b.first;
}
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  cin >> N >> M;

  vector<vector<pair<int, int>>> simp(N + 5);
  vector<pair<int, int>> v(N + 5);
  for (int i = 0; i < M; i++)
  {
    int a, b, c;
    cin >> a >> b >> c;
    simp[b].push_back({a, c});
  }
  for (int i = 1; i <= N; i++)
  {
    if (!simp[i].size())
      continue;
    sort(simp[i].begin(), simp[i].end(), comp);
    int cost = 0, val = 0;
    bool stat = true;
    for (auto j : simp[i])
    {
      if (!stat)
        break;
      int temp = j.second;
      for (int k = 0; k < temp; k++)
      {
        cost += i;
        val += j.first;
        // cout<<cost<<" "<<val<<endl;
        if (cost > N)
        {
          stat = false;
          break;
        }
        v.push_back({val, cost});
      }
    }
  }

  int dp[v.size() + 1][N + 1];
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i <= N; i++)
    dp[0][i] = 0;
  for (int i = 1; i <= N; i++)
  {
    dp[i][0] = dp[i - 1][0];
    if (v[i].size())
    {
      for (auto j : v[i])
      {
        for (int k = 1; k <= N; k++)
        {
          // cout<<k<<endl;
          if (k >= j.second)
          {
            dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - j.second] + j.first);
            // cout<<i<<" "<<k<<" "<<dp[i][k]<<" "<<dp[i-1][k-j.second]<<endl;
          }
          else
          {
            dp[i][k] = max(dp[i][k], dp[i - 1][k]);
          }
        }
      }
    }
    else
    {
      for (int k = 1; k <= N; k++)
      {
        dp[i][k] = dp[i - 1][k];
        // cout<<i<<" "<<k<<" "<<dp[i][k]<<" "<<dp[i-1][k]<<" "<<i-1<<" "<<k<<endl;
      }
    }
  }
  cout << dp[N][N] << endl;
  // dp[0][0]=0;
  // for(int i=1;i<=N;i++){
  //     if(tot[i]){
  //         for(int j=1;j<=N;j++){
  //             int idx=1, cur=v[i][idx].first, cur2=v[i][idx].second, sz=v[i].size();
  //             int k=0;

  //         }
  //     }
  // }
  return 0;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:79:14: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 'size'
   79 |     if (v[i].size())
      |              ^~~~
knapsack.cpp:81:24: error: no matching function for call to 'begin(std::pair<long long int, long long int>&)'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from knapsack.cpp:1:
/usr/include/c++/10/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
   90 |     begin(initializer_list<_Tp> __ils) noexcept
      |     ^~~~~
/usr/include/c++/10/initializer_list:90:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from knapsack.cpp:1:
/usr/include/c++/10/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:51:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&) [with _Container = std::pair<long long int, long long int>]':
knapsack.cpp:81:24:   required from here
/usr/include/c++/10/bits/range_access.h:51:50: error: 'struct std::pair<long long int, long long int>' has no member named 'begin'
   51 |     begin(_Container& __cont) -> decltype(__cont.begin())
      |                                           ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:61:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&) [with _Container = std::pair<long long int, long long int>]':
knapsack.cpp:81:24:   required from here
/usr/include/c++/10/bits/range_access.h:61:56: error: 'const struct std::pair<long long int, long long int>' has no member named 'begin'
   61 |     begin(const _Container& __cont) -> decltype(__cont.begin())
      |                                                 ~~~~~~~^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
   90 |     begin(_Tp (&__arr)[_Nm])
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:90:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from knapsack.cpp:1:
/usr/include/c++/10/valarray:1214:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
 1214 |     begin(valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1214:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from knapsack.cpp:1:
/usr/include/c++/10/valarray:1224:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
/usr/include/c++/10/valarray:1224:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
   81 |       for (auto j : v[i])
      |                        ^
knapsack.cpp:81:24: error: no matching function for call to 'end(std::pair<long long int, long long int>&)'
In file included from /usr/include/c++/10/bits/range_access.h:36,
                 from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from knapsack.cpp:1:
/usr/include/c++/10/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
  101 |     end(initializer_list<_Tp> __ils) noexcept
      |     ^~~
/usr/include/c++/10/initializer_list:101:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   'std::pair<long long int, long long int>' is not derived from 'std::initializer_list<_Tp>'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from knapsack.cpp:1:
/usr/include/c++/10/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:71:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&) [with _Container = std::pair<long long int, long long int>]':
knapsack.cpp:81:24:   required from here
/usr/include/c++/10/bits/range_access.h:71:48: error: 'struct std::pair<long long int, long long int>' has no member named 'end'
   71 |     end(_Container& __cont) -> decltype(__cont.end())
      |                                         ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |     ^~~
/usr/include/c++/10/bits/range_access.h:81:5: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/range_access.h: In substitution of 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&) [with _Container = std::pair<long long int, long long int>]':
knapsack.cpp:81:24:   required from here
/usr/include/c++/10/bits/range_access.h:81:54: error: 'const struct std::pair<long long int, long long int>' has no member named 'end'
   81 |     end(const _Container& __cont) -> decltype(__cont.end())
      |                                               ~~~~~~~^~~
/usr/include/c++/10/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
  100 |     end(_Tp (&__arr)[_Nm])
      |     ^~~
/usr/include/c++/10/bits/range_access.h:100:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   mismatched types '_Tp [_Nm]' and 'std::pair<long long int, long long int>'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from knapsack.cpp:1:
/usr/include/c++/10/valarray:1234:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
 1234 |     end(valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1234:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   'std::pair<long long int, long long int>' is not derived from 'std::valarray<_Tp>'
   81 |       for (auto j : v[i])
      |                        ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from knapsack.cpp:1:
/usr/include/c++/10/valarray:1244:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
/usr/include/c++/10/valarray:1244:5: note:   template argument deduction/substitution failed:
knapsack.cpp:81:24: note:   'std::pair<long long int, long long int>' is not derived from 'const std::valarray<_Tp>'
   81 |       for (auto j : v[i])
      |                        ^