QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#267240 | #4585. Greedy Knapsack | NYCU_Yamada | WA | 441ms | 13928kb | C++20 | 3.4kb | 2023-11-27 02:50:16 | 2023-11-27 02:50:16 |
Judging History
answer
#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada
const int B = 35;
const int maxc = 1 << 17;
set<pii> st[B];
int taw[B], tav[B];
int ans[maxc];
void solve() {
int n, t; cin >> n >> t;
vector<int> w(n), v(n);
for (auto &x : w) cin >> x;
for (auto &x : v) cin >> x;
int idx = 0;
for (int i = max(int(1), t - maxc); i <= t; ++i, ++idx) {
// debug(i);
int hb = __lg(i);
st[hb].ee(i, idx);
}
for (int i = 0; i < n; ++i) {
int hb = __lg(w[i]);
while (SZ(st[hb])) {
auto it = st[hb].end(); it = prev(it);
pii cur = *it;
if (cur.X - taw[hb] < w[i]) break;
else {
int nxtw = cur.X - w[i] - taw[hb];
st[hb].erase(it);
ans[cur.Y] += v[i] + tav[hb];
if (nxtw == 0) continue;
int nxthb = __lg(nxtw);
st[nxthb].ee(nxtw + taw[nxthb], cur.Y);
ans[cur.Y] -= tav[nxthb];
}
}
for (int j = hb + 1; j < B; ++j) {
taw[j] += w[i], tav[j] += v[i];
while (SZ(st[j])) {
auto it = st[j].begin();
pii cur = *it;
if (cur.X - taw[j] < (int(1) << j)) {
int nxtw = cur.X - taw[j];
int nxthb = __lg(nxtw);
st[j].erase(it);
st[nxthb].ee(nxtw + taw[nxthb], cur.Y);
ans[cur.Y] += tav[j] - tav[nxthb];
}
else break;
}
}
}
for (int i = 0; i < B; ++i) {
for (auto it : st[i]) ans[it.Y] += tav[i];
}
int tot = 0;
for (int i = 0; i < idx; ++i) chmax(tot, ans[i]);
print(tot);
}
signed main() {
IOS();
int t = 1; // cin >> t;
for (int i=1;i<=t;++i) solve();
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize ("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define double __float80
using pii = pair<int, int>;
template <typename T> using MaxHeap = std::priority_queue<T>;
template <typename T> using MinHeap = std::priority_queue<T, vector<T>, greater<T>>;
#define SZ(a) ((int)(a).size())
#define ALL(a) begin(a), end(a)
#define RALL(a) rbegin(a), rend(a)
#define ee emplace
#define eb emplace_back
#define ef emplace_front
#define pb pop_back
#define pf pop_front
#define X first
#define Y second
#ifdef local
#define IOS() void()
#define debug(...) \
fprintf(stderr, "\e[1;93m"), \
fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\e[0m")
template <typename T> void _do(T &&_t) {cerr << _t << '\n';}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#define print(...) \
fprintf(stderr, "\e[1;96m"), \
_P(__VA_ARGS__), \
fprintf(stderr, "\e[0m")
#else
#define IOS() ios_base::sync_with_stdio(0); cin.tie(0)
#define debug(...) void()
#define print(...) _P(__VA_ARGS__)
#define endl '\n'
#endif
template <typename U, typename V> bool chmin(U &u, V v) {return u > v ? u = v, 1 : 0;}
template <typename U, typename V> bool chmax(U &u, V v) {return u < v ? u = v, 1 : 0;}
template <typename T> void _P(T &&_x) {cout << _x << '\n';}
template <typename T, typename ...S> void _P(T &&_x, S &&..._t) {cout << _x << " "; _P(_t...);}
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
5 10 10 1 2 3 4 1 1 1 1 1
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 12ms
memory: 12740kb
input:
5 10000000000 10 1 2 3 4 30 2 15 7 11
output:
65
result:
ok single line: '65'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
5 20 4 9 5 1 3 203 175 131 218 304
output:
900
result:
ok single line: '900'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
1 1 1 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 52ms
memory: 13864kb
input:
100000 200000 100000 99998 99996 99994 99992 99990 99988 99986 99984 99982 99980 99978 99976 99974 99972 99970 99968 99966 99964 99962 99960 99958 99956 99954 99952 99950 99948 99946 99944 99942 99940 99938 99936 99934 99932 99930 99928 99926 99924 99922 99920 99918 99916 99914 99912 99910 99908 999...
output:
100002
result:
ok single line: '100002'
Test #6:
score: -100
Wrong Answer
time: 441ms
memory: 13928kb
input:
92455 883403359 82193 96168 42737 25557 5699 8922 41136 82789 26249 74241 57030 29989 41743 78491 37281 60598 23165 51802 13911 88911 55220 25398 60154 2879 14519 61138 16806 15952 83710 44076 43551 41425 11055 3321 59105 34722 60133 13735 36785 73444 92250 3613 35787 10798 35612 9564 42531 49012 83...
output:
1761282608
result:
wrong answer 1st lines differ - expected: '881743221', found: '1761282608'