Submission #1100455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100455		baoheyhey	Knapsack (NOI18_knapsack)	C++17	100 / 100	42 ms	1728 KiB

knapsack

#include<bits/stdc++.h>
#define FOR(i, l, r) for(int i = (l), _r = (r); i <= _r; ++i)
#define FOD(i, l, r) for(int i = (l), _r = (r); i >= _r; --i)
#define REP(i, n) for(int i = 1;  i <= (n); ++i)
#define RED(i, n) for(int i = n; i >= 1; --i)
#define ll long long 
#define ALL(a) a.begin(), a.end()
#define sz(a) a.size()
#define file(name) if(fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define el "\n"
#define bit(a, x) (a >> x & 1)
#define X first
#define Y second
#define TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define pb push_back
#define cntbit(x) __builtin_popcountll(x)
#define uni(a) sort(ALL(a)), a.resize(unique(ALL(a)) - a.begin())
using namespace std;

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;

const int maxn = 2005;

ll dp[2005];
vector<pii> a[maxn];
int s, n, v, w, k;

signed main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> s >> n;
	FOR(i, 1, n){
		cin >> v >> w >> k;
		a[w].pb({v, k});
	}
	ll ans = 0;
	FOR(i, 1, s){
		sort(ALL(a[i]), greater<pii> ());
		int id = 0;
		FOR(j, 1, s / i){
			if(id >= sz(a[i])) break;
			FOD(k, s, i){
				dp[k] = max(dp[k], dp[k - i] + a[i][id].X);
				ans = max(ans, dp[k]);
			}
			a[i][id].Y--;
			if(a[i][id].Y == 0) ++id;
		}
	}
	//FOR(i, 1, s) cout << dp[i] << ' ';
	cout << ans;
	cerr << "Time elapsed: " << TIME << " s" << el;
}

Compilation message (stderr)

knapsack.cpp: In function 'int main()':
knapsack.cpp:44:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    if(id >= sz(a[i])) break;
      |          ^

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