Submission #1312248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312248		joesephdiver	Knapsack (NOI18_knapsack)	C++20	12 / 100	1 ms	572 KiB

knapsack

#include <algorithm>
#include <bits/stdc++.h>
#include <queue>
using namespace std;

template<class T> using V = vector<T>;

using ll  = long long;
using ull = unsigned long long;
using ld  = long double;

using pii = pair<int,int>;
using pll = pair<ll,ll>;

using vi = V<int>;
using vll = V<ll>;

#define all(x)  begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x)   (int)((x).size())

#define pb  push_back
#define eb  emplace_back
#define mp  make_pair

#define rep(i,n)    for (int i = 0; i < (int)(n); ++i)
#define rep1(i,n)   for (int i = 1; i <= (int)(n); ++i)
#define forr(i,a,b) for (int i = (a); i <= (int)(b); ++i)
#define rfor(i,a,b) for (int i = (a); i >= (int)(b); --i)

const ll  INF64 = (1LL<<62) - 1;
const int INF   = 0x3f3f3f3f;    
const int MOD   = 1'000'000'007;

struct FastIO {
  FastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.setf(std::ios::fixed); cout.precision(12);
  }
} fastio;

inline void setIO(const string& inFile, const string& outFile){
  if (!inFile.empty())  assert(freopen(inFile.c_str(), "r", stdin)  != nullptr);
  if (!outFile.empty()) assert(freopen(outFile.c_str(), "w", stdout) != nullptr);
}

inline void setIO(const string& base){
  setIO(base + ".in", base + ".out");
}

template <class T, class U>
struct PairHash {
    std::size_t operator()(const std::pair<T, U>& p) const noexcept {
        std::size_t h1 = std::hash<T>{}(p.first);
        std::size_t h2 = std::hash<U>{}(p.second);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

template<class T> inline bool chmin(T& a, const T& b){ if(b < a){ a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, const T& b){ if(a < b){ a = b; return true; } return false; }

template<class T> inline T ceil_div(T a, T b){
  return (a>=0 ? (a + b - 1)/b : a/b);
}
template<class T> inline T floor_div(T a, T b){
  return (a>=0 ? a/b : (a - b + 1)/b);
}

template<class T> inline T clampv(T x, T lo, T hi){ return x < lo ? lo : (x > hi ? hi : x); }

template<class T> string to_str(const T& x){ std::ostringstream os; os << x; return os.str(); }

ll modpow(ll a, ll e, ll m=MOD){
  ll r = 1; a %= m; while(e){ if(e&1) r = (__int128)r*a % m; a = (__int128)a*a % m; e >>= 1; }
  return r;
}

template<class T>
vector<int> compress(const vector<T>& a, vector<T>* values_out=nullptr){
  vector<T> v = a; sort(all(v)); v.erase(unique(all(v)), v.end());
  if(values_out) *values_out = v;
  vector<int> id(a.size());
  rep(i, a.size()) id[i] = (int)(lower_bound(all(v), a[i]) - v.begin());
  return id;
}

template<class T> istream& operator>>(istream& is, vector<T>& v){ for (auto& x : v) is >> x; return is; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& v){
  for (int i = 0; i < sz(v); ++i) os << v[i] << (i+1==sz(v) ? "" : " ");
  return os;
}

struct DSU {
    V<int> e; void init(int N) { e = V<int>(N,-1); }
    int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } 
    bool sameSet(int a, int b) { return get(a) == get(b); }
    int size(int x) { return -e[get(x)]; }
    bool unite(int x, int y) {
        x = get(x), y = get(y); if (x == y) return 0;
        if (e[x] > e[y]) swap(x,y);
        e[x] += e[y]; e[y] = x; return 1;
    }
};

const int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};
const int dx8[8] = {1,1,0,-1,-1,-1,0,1}, dy8[8] = {0,1,1,1,0,-1,-1,-1};
const int kx[8]  = {1,2,2,1,-1,-2,-2,-1}, ky[8] = {2,1,-1,-2,-2,-1,1,2};

int mod = 1000000007;

struct item{
	ll value, weight, copies;
};

int main(){
	int s, n;
	cin >> s >> n;
	V<item> v(n);
	rep(i, n){
		cin >> v[i].value >> v[i].weight >> v[i].copies;
	}
	ll dp[s+1]{};
	//each item
	for(int i = 0; i < n; i++){
		int copies[s+1]{};
		for(int w = 0; w <= s-v[i].weight; w++){
			if(copies[w] < v[i].copies && chmax(dp[w+v[i].weight], dp[w]+v[i].value)){
				//copies of item i used
				copies[w+v[i].weight] = copies[w]+1;
			}
		}
	}
	cout << *max_element(dp, dp+s+1) << endl;
}

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