# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
993121 | cpdreamer | Knapsack (NOI18_knapsack) | C++17 | 1 ms | 348 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <utility>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
const int max_n=INT_MAX;
typedef long long ll;
#define LLM LONG_LONG_MAX
#define pb push_back
#define F first
#define L length()
#define all(v) v.begin(),v.end()
#define P pair
#define V vector
#define S second
const long long MOD = 1000000007; // 1e9 + 7
void file(){
freopen("input.txt.txt","r",stdin);
freopen("output.txt.txt","w",stdout);
}
void setio(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
bool is_sorted(ll A[],ll n) {
for (ll i = 0; i < n - 1; i++) {
if (A[i] > A[i + 1])
return false;
}
return true;
}
void solve() {
ll W, n;
cin >> W >> n;
ll v[n], k[n], w[n];
V<V<P<ll, ll>>> vp(W + 1);
V<V<P<ll, ll>>> pref(W + 1);
for (ll i = 0; i < n; i++) {
cin >> v[i] >> w[i] >> k[i];
vp[w[i]].pb({v[i], k[i]});
}
ll dp[W + 1];
bool made[W + 1];
memset(dp, -1, sizeof(dp));
memset(made, false, sizeof(dp));
dp[0] = 0;
made[0] = true;
for (ll i = 1; i <= W; i++) {
sort(all(vp[i]));
reverse(all(vp[i]));
}
for (ll i = 1; i <= W; i++) {
if (!vp[i].empty()) {
pref[i].pb({vp[i][0].F*vp[i][0].S,vp[i][0].S});
for (ll j = 1; j < vp[i].size(); j++) {
pref[i].pb({vp[i][j].F*vp[i][j].S + pref[i][j - 1].F, vp[i][j].S + pref[i][j - 1].S});
}
}
}
for (ll i = 1; i <= W; i++) {
if (!vp[i].empty()) {
for (ll j = W; j >= i; j--) {
ll weight = j;
ll l = 0, r = (ll)pref[i].size() - 1;
ll ans = -1;
while (l <= r) {
ll m = l + (r - l) / 2;
if (pref[i][m].S * i >= j) {
ans = m;
r = m - 1;
} else
l = m + 1;
}
if (ans == -1)
ans = (ll) vp[i].size() - 1;
ll a = 0;
ll value=0;
if (ans > 0) {
a = (ll) pref[i][ans - 1].S * i;
value = (ll) pref[i][ans - 1].F;
}
weight -= a;
ll add = min((weight / i),(ll)vp[i][ans].S);
a += add*i;
value+=(ll) vp[i][ans].F * add;
if (made[j - a]) {
made[j] = true;
dp[j] = max(dp[j], dp[j - a] + value);
}
}
}
}
cout << *max_element(dp, dp + W + 1) << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//file();
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |