| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 873169 | Squar_Head | Knapsack (NOI18_knapsack) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define lop(i,a,b) for(ll i = a; i < b; i++)
#define alop(i,v) for(auto &i: v)
#define in(v) for(auto &i: v) cin >> i;
#define ll long long
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(dp, x) memset(dp, x, sizeof(dp))
#define F first
#define S second
using namespace std;
ll mod = 2019;
const ll N = 1e5;
bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
signed main()
{
int n, s; cin >> s >> n;
vector<array<ll, 3>> v(n); // {value, weight, copies}
vector<vector<ll>> tt(s + 1);
vector<pair<ll, ll>> arr(1);
alop(i, v){
in(i);
ll temp = (s / i[1]) + 1, p = 1;
while(i[2] > 0 && temp > 0){
tt[i[1] * p].pb(i[0] * p);
i[2] -= p, temp -= p;
if(i[2] - (p + 1) >= 0 && temp - (p + 1) >= 0) p++;
else p = min(i[2], temp);
}
}
for(ll i = 1; i <= s; i++){
sort(all(tt[i]), greater<ll>());
lop(j, 0, min((s / i) + 2, (ll)tt[i].size())) arr.pb({tt[i][j], i});
}
n = arr.size() - 1;
ll dp[n + 1][s + 1] = {};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= s; j++){
dp[i][j] = dp[i - 1][j];
if(j - arr[i].second >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i].second] + arr[i].first);
}
}
cout << dp[n][s];
return 0;
}#include <bits/stdc++.h>
#define lop(i,a,b) for(ll i = a; i < b; i++)
#define alop(i,v) for(auto &i: v)
#define in(v) for(auto &i: v) cin >> i;
#define ll long long
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(dp, x) memset(dp, x, sizeof(dp))
#define F first
#define S second
using namespace std;
ll mod = 2019;
const ll N = 1e5;
bool cmp(pair<ll, ll> a, pair<ll, ll> b) {
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
signed main()
{
int n, s; cin >> s >> n;
vector<array<ll, 3>> v(n); // {value, weight, copies}
vector<vector<ll>> tt(s + 1);
vector<pair<ll, ll>> arr(1);
alop(i, v){
in(i);
ll temp = (s / i[1]) + 1, p = 1;
while(i[2] > 0 && temp > 0){
tt[i[1] * p].pb(i[0] * p);
i[2] -= p, temp -= p;
if(i[2] - (p + 1) >= 0 && temp - (p + 1) >= 0) p++;
else p = min(i[2], temp);
}
}
for(ll i = 1; i <= s; i++){
sort(all(tt[i]), greater<ll>());
lop(j, 0, min((s / i) + 2, (ll)tt[i].size())) arr.pb({tt[i][j], i});
}
n = arr.size() - 1;
ll dp[n + 1][s + 1] = {};
for(int i = 1; i <= n; i++){
for(int j = 1; j <= s; j++){
dp[i][j] = dp[i - 1][j];
if(j - arr[i].second >= 0) dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i].second] + arr[i].first);
}
}
cout << dp[n][s];
return 0;
}