Submission #1101834

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

knapsack

#include<bits/stdc++.h>
 
using ll = long long;
using pii = pair<long long,int>;
 
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll mod = 1e9 + 7;

const int maxn = 1e5 + 5;

void solve(){
 ll s;
 int n;
 cin >> s >> n;
 map<int, vector<pii>> mp;
 REP(i, n){
  int v, w, k;
  cin >> v >> w >> k;
  mp[w].pb({v, k});
 }
 int m = mp.size();
 vector<vector<ll>> dp(m + 1, vector<ll> (s + 1));
 int cur = 0;
 for (auto [w, v] : mp){
  vector<pii> a = v;
  sort(a.begin(), a.end(), [](pii x, pii y){
    return x.fi > y.fi;
  });
  for (int i = 0; i <= s; i++){
    chmax(dp[cur + 1][i], dp[cur][i]);
  }
  int idx1 = 0;
  int idx2 = 0;
  int cnt = 1;
  ll weight;
  ll val = 0;
  while(true){
    weight = cnt * w;
    val += a[idx2].fi;
    idx1++;
    if (weight > s) break;
    for (int i = 0; i + weight <= s; i++){
      chmax(dp[cur + 1][i + weight], dp[cur][i] + val);
    }
    if (idx1 == a[idx2].se){
      idx2++;
      if (idx2 == a.size()){
        break;
      }
      idx1 = 0;
    }
    cnt++;
  }
  cur++;
 }
  cout << *max_element(all(dp[m - 1]));
}
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    el;
  }
  return 0;
}

Compilation message (stderr)

knapsack.cpp:4:13: error: 'pair' does not name a type
    4 | using pii = pair<long long,int>;
      |             ^~~~
knapsack.cpp:17:1: error: 'mt19937' does not name a type
   17 | mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
      | ^~~~~~~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:26:2: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
   26 |  cin >> s >> n;
      |  ^~~
      |  std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from knapsack.cpp:1:
/usr/include/c++/10/iostream:60:18: note: 'std::cin' declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
knapsack.cpp:27:2: error: 'map' was not declared in this scope
   27 |  map<int, vector<pii>> mp;
      |  ^~~
knapsack.cpp:27:2: note: suggested alternatives:
In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from knapsack.cpp:1:
/usr/include/c++/10/bits/stl_map.h:100:11: note:   'std::map'
  100 |     class map
      |           ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from knapsack.cpp:1:
/usr/include/c++/10/map:78:13: note:   'std::pmr::map'
   78 |       using map
      |             ^~~
knapsack.cpp:27:6: error: expected primary-expression before 'int'
   27 |  map<int, vector<pii>> mp;
      |      ^~~
knapsack.cpp:31:3: error: 'mp' was not declared in this scope
   31 |   mp[w].pb({v, k});
      |   ^~
knapsack.cpp:33:10: error: 'mp' was not declared in this scope; did you mean 'm'?
   33 |  int m = mp.size();
      |          ^~
      |          m
knapsack.cpp:34:2: error: 'vector' was not declared in this scope
   34 |  vector<vector<ll>> dp(m + 1, vector<ll> (s + 1));
      |  ^~~~~~
knapsack.cpp:34:2: note: suggested alternatives:
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:389:11: note:   'std::vector'
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included 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/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
knapsack.cpp:34:18: error: expected primary-expression before '>>' token
   34 |  vector<vector<ll>> dp(m + 1, vector<ll> (s + 1));
      |                  ^~
knapsack.cpp:34:40: error: expected primary-expression before '>' token
   34 |  vector<vector<ll>> dp(m + 1, vector<ll> (s + 1));
      |                                        ^
knapsack.cpp:34:21: error: 'dp' was not declared in this scope
   34 |  vector<vector<ll>> dp(m + 1, vector<ll> (s + 1));
      |                     ^~
knapsack.cpp:37:10: error: 'pii' was not declared in this scope
   37 |   vector<pii> a = v;
      |          ^~~
knapsack.cpp:37:15: error: 'a' was not declared in this scope
   37 |   vector<pii> a = v;
      |               ^
knapsack.cpp:38:31: error: 'pii' is not a type
   38 |   sort(a.begin(), a.end(), [](pii x, pii y){
      |                               ^~~
knapsack.cpp:38:38: error: 'pii' is not a type
   38 |   sort(a.begin(), a.end(), [](pii x, pii y){
      |                                      ^~~
knapsack.cpp: In lambda function:
knapsack.cpp:7:12: error: request for member 'first' in 'x', which is of non-class type 'int'
    7 | #define fi first
      |            ^~~~~
knapsack.cpp:39:14: note: in expansion of macro 'fi'
   39 |     return x.fi > y.fi;
      |              ^~
knapsack.cpp:7:12: error: request for member 'first' in 'y', which is of non-class type 'int'
    7 | #define fi first
      |            ^~~~~
knapsack.cpp:39:21: note: in expansion of macro 'fi'
   39 |     return x.fi > y.fi;
      |                     ^~
knapsack.cpp: In function 'void solve()':
knapsack.cpp:38:3: error: 'sort' was not declared in this scope; did you mean 'std::sort'?
   38 |   sort(a.begin(), a.end(), [](pii x, pii y){
      |   ^~~~
      |   std::sort
In file included 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/pstl/glue_algorithm_defs.h:296:1: note: 'std::sort' declared here
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
knapsack.cpp:68:3: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
   68 |   cout << *max_element(all(dp[m - 1]));
      |   ^~~~
      |   std::cout
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from knapsack.cpp:1:
/usr/include/c++/10/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~
knapsack.cpp:68:12: error: 'max_element' was not declared in this scope; did you mean 'std::max_element'?
   68 |   cout << *max_element(all(dp[m - 1]));
      |            ^~~~~~~~~~~
      |            std::max_element
In file included 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/pstl/glue_algorithm_defs.h:528:1: note: 'std::max_element' declared here
  528 | max_element(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last);
      | ^~~~~~~~~~~
knapsack.cpp: In function 'int32_t main()':
knapsack.cpp:72:3: error: 'ios_base' has not been declared
   72 |   ios_base::sync_with_stdio(false);
      |   ^~~~~~~~
knapsack.cpp:73:3: error: 'cin' was not declared in this scope; did you mean 'std::cin'?
   73 |   cin.tie(NULL);
      |   ^~~
      |   std::cin
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from knapsack.cpp:1:
/usr/include/c++/10/iostream:60:18: note: 'std::cin' declared here
   60 |   extern istream cin;  /// Linked to standard input
      |                  ^~~
knapsack.cpp:77:5: error: 'cerr' was not declared in this scope; did you mean 'std::cerr'?
   77 |     cerr << "- Case #" << _ << ": \n";
      |     ^~~~
      |     std::cerr
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from knapsack.cpp:1:
/usr/include/c++/10/iostream:62:18: note: 'std::cerr' declared here
   62 |   extern ostream cerr;  /// Linked to standard error (unbuffered)
      |                  ^~~~
knapsack.cpp:6:12: error: 'cout' was not declared in this scope; did you mean 'std::cout'?
    6 | #define el cout << '\n'
      |            ^~~~
knapsack.cpp:79:5: note: in expansion of macro 'el'
   79 |     el;
      |     ^~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:75,
                 from knapsack.cpp:1:
/usr/include/c++/10/iostream:61:18: note: 'std::cout' declared here
   61 |   extern ostream cout;  /// Linked to standard output
      |                  ^~~~