Kiện vở (Đề tự luyện HSG Tin 12 – Bài 5)
Đề bài
Kiện vở. Dọc con kênh có $N$ bến; bến $i$ có một kiện vở nặng $w_i$ kg gồm $v_i$ quyển (chỉ nhận nguyên kiện hoặc không nhận). Có $Q$ phương án, phương án $j$: đi qua các bến $l_j, l_j + 1, \dots, r_j$, mỗi bến được chọn nhận hoặc không nhận kiện vở của bến đó, tổng khối lượng nhận không vượt quá $c_j$. Với mỗi phương án, in số quyển vở nhiều nhất nhận được (các phương án độc lập).
Dữ liệu vào: dòng đầu $N, Q$ ($1 \le N \le 3 \cdot 10^4$, $1 \le Q \le 5 \cdot 10^4$); $N$ dòng $w_i, v_i$ ($1 \le w_i \le 100$, $1 \le v_i \le 10^9$); $Q$ dòng $l_j, r_j, c_j$ ($1 \le l_j \le r_j \le N$, $1 \le c_j \le 100$).
Kết quả: $Q$ dòng, dòng $j$ là đáp án của phương án $j$.
- Subtask 1 (10%): $N \le 100$ và $Q \le 100$.
- Subtask 2 (15%): $l_j = 1$ với mọi $j$.
- Subtask 3 (20%): $N \le 3000$.
- Subtask 4 (25%): mọi phương án đều đi qua bến $m = \lfloor (N + 1) / 2 \rfloor$ ($l_j \le m \le r_j$).
- Subtask 5 (30%): không có ràng buộc gì thêm.
8 5
7 55
4 35
7 52
4 22
4 27
5 14
5 28
4 10
1 5 11
5 7 9
2 2 3
6 8 9
3 8 990
55
0
38
55Phương án 1: nhận kiện bến $1, 2$ ($11$ kg, $90$ quyển). Phương án 2: bến $5, 7$ ($55$ quyển). Phương án 3: kiện bến $2$ nặng $4 > 3$ kg, không nhận được gì. Phương án 4: bến $7, 8$ ($38$ quyển). Phương án 5: bến $5, 7$ ($55$ quyển); nếu nhận kiện bến $3$ ($52$ quyển, $7$ kg) thì không chở thêm được kiện nào.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Kiện vởLời mở đầu
Đây là bài phân loại cuối đề. Mỗi phương án, tách riêng ra, chỉ là bài cái túi 0/1 quen thuộc: các kiện vở của đoạn $[l, r]$, sức chứa $c$. Cái khó là có tới $5 \cdot 10^4$ phương án trên dãy $3 \cdot 10^4$ bến: giải từng cái mất $Q \cdot N \cdot c \approx 1{,}5 \cdot 10^{11}$ phép tính.
Với các bài "truy vấn tổng trên đoạn", ta hay dùng tổng tiền tố rồi trừ đi. Nhưng cái túi không trừ được: biết đáp án của các bến $1..r$ và $1..(l-1)$ không giúp gì cho đoạn $l..r$. Cái túi chỉ cho phép hai thao tác:
- Thêm một kiện vào một bảng QHĐ: $O(c)$.
- Ghép hai bảng của hai phần rời nhau: nếu $A[x]$ là số vở nhiều nhất của phần trái với khối lượng $\le x$ và $B[y]$ là của phần phải với khối lượng $\le y$, thì đáp án của cả hai phần với sức chở $c$ là $\max_{x = 0}^{c} \big(A[x] + B[c - x]\big)$: chỉ $O(c)$ cho một giá trị $c$.
Một phương án đi qua điểm chia được tách làm hai nửa rời nhau; mỗi nửa là một bảng "mọc dần" từ điểm chia ra hai phía.
Ý tưởng cuối cùng: chọn một điểm chia, chuẩn bị sẵn bảng cho mọi "nửa" bắt đầu từ điểm chia, rồi mỗi phương án đi qua điểm chia chỉ tốn $O(c)$. Các phương án không đi qua điểm chia thì nằm gọn bên trái hoặc bên phải — ta giải tiếp hai bên bằng cách y hệt: chia để trị. Mình đi qua 5 cách, mỗi cách ứng với một subtask:
Cách 1Giải cái túi cho từng phương án – O(Q · N · c) · 10%
Với mỗi phương án, gọi $dp[x]$ là số vở nhiều nhất với tổng khối lượng không quá $x$ (ban đầu toàn $0$). Lần lượt xét kiện $i = l..r$: duyệt $x$ giảm dần từ $c$ về $w_i$, $dp[x] = \max(dp[x], dp[x - w_i] + v_i)$. Duyệt giảm dần để mỗi kiện chỉ được lấy một lần (duyệt tăng dần thì $dp[x - w_i]$ có thể đã chứa chính kiện $i$).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> w(n + 1);
vector<ll> v(n + 1);
for (int i = 1; i <= n; i++) scanf("%d %lld", &w[i], &v[i]);
while (q--) {
int l, r, c;
scanf("%d %d %d", &l, &r, &c);
vector<ll> dp(c + 1, 0); // dp[x]: nhiều vở nhất với tổng khối lượng <= x
for (int i = l; i <= r; i++) // cái túi 0/1 trên các bến l..r
for (int x = c; x >= w[i]; x--) dp[x] = max(dp[x], dp[x - w[i]] + v[i]);
printf("%lld\n", dp[c]);
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
w = [0] * (n + 1); v = [0] * (n + 1)
p = 2
for i in range(1, n + 1):
w[i] = int(data[p]); v[i] = int(data[p + 1]); p += 2
out = []
for _ in range(q):
l, r, c = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
dp = [0] * (c + 1) # dp[x]: nhiều vở nhất với tổng khối lượng <= x
for i in range(l, r + 1): # cái túi 0/1 trên các bến l..r
for x in range(c, w[i] - 1, -1):
if dp[x - w[i]] + v[i] > dp[x]:
dp[x] = dp[x - w[i]] + v[i]
out.append(dp[c])
print("\n".join(map(str, out)))
main()Cách 2Mọi phương án bắt đầu từ bến 1: bảng tiền tố – O(N · c + Q) · 15%
Khi $l = 1$, phương án chỉ phụ thuộc $r$ và $c$. Tính trước $pre[i][x]$ = đáp án khi dùng các bến $1..i$ với khối lượng $\le x$ ($x \le 100$): $pre[i] = pre[i - 1]$ "thêm kiện $i$". Mỗi phương án trả lời ngay $pre[r][c]$. Bảng có $N \cdot 101$ số long long (khoảng $24$ MB).
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int W = 100;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> w(n + 1);
vector<ll> v(n + 1);
for (int i = 1; i <= n; i++) scanf("%d %lld", &w[i], &v[i]);
// pre[i][x]: chỉ dùng các bến 1..i, tổng khối lượng <= x
vector<vector<ll>> pre(n + 1, vector<ll>(W + 1, 0));
for (int i = 1; i <= n; i++)
for (int x = 0; x <= W; x++) {
pre[i][x] = pre[i - 1][x];
if (x >= w[i]) pre[i][x] = max(pre[i][x], pre[i - 1][x - w[i]] + v[i]);
}
while (q--) {
int l, r, c;
scanf("%d %d %d", &l, &r, &c); // subtask 2: l luôn bằng 1
printf("%lld\n", pre[r][c]);
}
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
W = 100
pre = [[0] * (W + 1)] # pre[i][x]: chỉ dùng các bến 1..i, khối lượng <= x
p = 2
for i in range(1, n + 1):
wi, vi = int(data[p]), int(data[p + 1]); p += 2
a = pre[-1]
b = a[:]
for x in range(wi, W + 1):
if a[x - wi] + vi > b[x]:
b[x] = a[x - wi] + vi
pre.append(b)
out = []
for _ in range(q):
l, r, c = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
out.append(pre[r][c]) # subtask 2: l luôn bằng 1
print("\n".join(map(str, out)))
main()Cách 3Gom các phương án cùng bến xuất phát – O(N² · c + Q log Q) · 45%
Tổng quát hóa Cách 2: sắp xếp phương án theo $(l, r)$. Với mỗi giá trị $l$ xuất hiện, bắt đầu một bảng $dp$ toàn $0$, thêm dần kiện $l, l + 1, \dots$ và khi vừa thêm xong kiện $r$ thì trả lời mọi phương án $(l, r, c)$ bằng $dp[c]$. Mỗi giá trị $l$ quét tối đa $N$ kiện, nên tổng $O(N^2 \cdot c)$: với $N \le 3000$ là không quá $4{,}5 \cdot 10^8$ phép tính rất đơn giản (cộng, so sánh), C++ chạy kịp. Cách này đúng luôn cho subtask 1 và 2 (cộng lại $45\%$), nhưng với $N = 3 \cdot 10^4$ thì cần cỡ $4{,}5 \cdot 10^{10}$ phép tính — quá chậm.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> w(n + 1);
vector<ll> v(n + 1);
for (int i = 1; i <= n; i++) scanf("%d %lld", &w[i], &v[i]);
vector<int> l(q), r(q), c(q), id(q);
int W = 0;
for (int j = 0; j < q; j++) { scanf("%d %d %d", &l[j], &r[j], &c[j]); W = max(W, c[j]); id[j] = j; }
sort(id.begin(), id.end(), [&](int a, int b) { return l[a] != l[b] ? l[a] < l[b] : r[a] < r[b]; });
vector<ll> ans(q), dp(W + 1);
for (int k = 0; k < q; ) {
int L = l[id[k]], cur = L - 1;
fill(dp.begin(), dp.end(), 0);
for (; k < q && l[id[k]] == L; k++) { // các phương án cùng bến xuất phát L, r tăng dần
int j = id[k];
while (cur < r[j]) { // thêm dần kiện vở của bến cur + 1
cur++;
for (int x = W; x >= w[cur]; x--) dp[x] = max(dp[x], dp[x - w[cur]] + v[cur]);
}
ans[j] = dp[c[j]];
}
}
for (int j = 0; j < q; j++) printf("%lld\n", ans[j]);
}import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
w = [0] * (n + 1); v = [0] * (n + 1)
p = 2
for i in range(1, n + 1):
w[i] = int(data[p]); v[i] = int(data[p + 1]); p += 2
L = []; R = []; C = []
for _ in range(q):
L.append(int(data[p])); R.append(int(data[p + 1])); C.append(int(data[p + 2])); p += 3
W = max(C)
order = sorted(range(q), key=lambda j: (L[j], R[j]))
ans = [0] * q
k = 0
while k < q:
start = L[order[k]]; cur = start - 1
dp = [0] * (W + 1)
while k < q and L[order[k]] == start: # các phương án cùng bến xuất phát, r tăng dần
j = order[k]
while cur < R[j]: # thêm dần kiện vở của bến cur + 1
cur += 1
wi, vi = w[cur], v[cur]
for x in range(W, wi - 1, -1):
if dp[x - wi] + vi > dp[x]:
dp[x] = dp[x - wi] + vi
ans[j] = dp[C[j]]
k += 1
print("\n".join(map(str, ans)))
main()Cách 4Mọi phương án đi qua bến m: ghép hai nửa – O(N · c + Q · c) · 25%
Subtask 4 là "gợi ý" cho lời giải cuối. Đặt $m = \lfloor (N + 1)/2 \rfloor$. Mọi phương án có $l \le m \le r$ nên tách được thành hai phần rời nhau: các bến $l..m$ và các bến $(m + 1)..r$ (phần sau có thể rỗng khi $r = m$). Tính trước:
- $F[i]$ với $i \le m$: bảng của các bến $i..m$. $F[m]$ = chỉ kiện $m$; $F[i]$ = $F[i + 1]$ thêm kiện $i$ (đi từ $m$ ngược về $1$).
- $F[i]$ với $i > m$: bảng của các bến $(m + 1)..i$. $F[m + 1]$ = chỉ kiện $m + 1$; $F[i]$ = $F[i - 1]$ thêm kiện $i$.
Mỗi bảng là "khối lượng $\le x$" nên phương án $(l, r, c)$ có đáp án $\max_{x=0}^{c} F[l][x] + F[r][c - x]$ (khi $r = m$ thì bảng phải là bảng toàn $0$).
Nhiều bạn quen QHĐ "khối lượng đúng bằng $x$" (khởi tạo $-\infty$ trừ ô $0$). Khi ghép hai nửa như trên, cách đó chỉ xét các lựa chọn có tổng khối lượng đúng bằng $c$ — sai khi lựa chọn tốt nhất không chở đầy xuồng. Ví dụ của đề tình cờ đều "chở vừa khít" nên vẫn ra đúng, nhưng bộ test thì không!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int W = 100;
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> w(n + 2);
vector<ll> v(n + 2);
for (int i = 1; i <= n; i++) scanf("%d %lld", &w[i], &v[i]);
int m = (n + 1) / 2; // subtask 4: mọi phương án đều đi qua bến m
// F[i] (i <= m): các kiện từ bến i tới bến m; F[i] (i > m): các kiện từ bến m+1 tới bến i
vector<vector<ll>> F(n + 2, vector<ll>(W + 1, 0));
vector<ll> zero(W + 1, 0);
for (int i = m; i >= 1; i--) {
const vector<ll> &src = (i == m) ? zero : F[i + 1];
for (int x = 0; x <= W; x++) {
F[i][x] = src[x];
if (x >= w[i]) F[i][x] = max(F[i][x], src[x - w[i]] + v[i]);
}
}
for (int i = m + 1; i <= n; i++) {
const vector<ll> &src = (i == m + 1) ? zero : F[i - 1];
for (int x = 0; x <= W; x++) {
F[i][x] = src[x];
if (x >= w[i]) F[i][x] = max(F[i][x], src[x - w[i]] + v[i]);
}
}
while (q--) {
int l, r, c;
scanf("%d %d %d", &l, &r, &c);
const vector<ll> &A = F[l], &B = (r == m) ? zero : F[r];
ll best = 0;
for (int x = 0; x <= c; x++) best = max(best, A[x] + B[c - x]); // ghép hai nửa
printf("%lld\n", best);
}
}import sys
def add_item(src, wi, vi):
dst = src[:]
for x in range(wi, len(src)):
if src[x - wi] + vi > dst[x]:
dst[x] = src[x - wi] + vi
return dst
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
W = 100
w = [0] * (n + 2); v = [0] * (n + 2)
p = 2
for i in range(1, n + 1):
w[i] = int(data[p]); v[i] = int(data[p + 1]); p += 2
m = (n + 1) // 2 # subtask 4: mọi phương án đều đi qua bến m
zero = [0] * (W + 1)
F = [zero] * (n + 2)
F[m] = add_item(zero, w[m], v[m]) # F[i] (i <= m): các kiện từ bến i tới bến m
for i in range(m - 1, 0, -1):
F[i] = add_item(F[i + 1], w[i], v[i])
prev = zero # F[i] (i > m): các kiện từ bến m + 1 tới bến i
for i in range(m + 1, n + 1):
prev = F[i] = add_item(prev, w[i], v[i])
out = []
for _ in range(q):
l, r, c = int(data[p]), int(data[p + 1]), int(data[p + 2]); p += 3
A = F[l]
B = zero if r == m else F[r]
out.append(max(A[x] + B[c - x] for x in range(c + 1))) # ghép hai nửa
print("\n".join(map(str, out)))
main()Mô phỏng: chọn một phương án đi qua bến $m$, xem hai bảng mọc ra hai phía và phép ghép $A[x] + B[c - x]$.
Cách 5Chia để trị trên các phương án – O(N log N · c + Q · c) · 100%
Bây giờ phương án có thể nằm ở bất cứ đâu. Áp dụng Cách 4 một cách đệ quy: xét đoạn bến $[lo, hi]$ cùng danh sách các phương án nằm gọn trong đoạn này, lấy $mid = \lfloor (lo + hi)/2 \rfloor$ và chia các phương án làm ba nhóm:
- $r \le mid$: nằm gọn bên trái → để dành cho đoạn $[lo, mid]$;
- $l > mid$: nằm gọn bên phải → để dành cho đoạn $[mid + 1, hi]$;
- còn lại ($l \le mid < r$): đi qua điểm chia → giải ngay như Cách 4, với nửa trái là các bến $l..mid$, nửa phải là các bến $(mid + 1)..r$.
Phương án có $l = r$ (chỉ một bến) thì trả lời trực tiếp ngay từ đầu: nhận được nếu $w_l \le c$.
Ở mỗi "tầng" chia đôi, các đoạn rời nhau, nên tổng số lần "thêm một kiện" ở một tầng không quá $N$, mỗi lần $O(c)$. Có $\lceil \log_2 N \rceil \approx 15$ tầng, vậy phần chuẩn bị tốn $O(N \log N \cdot c) \approx 3 \cdot 10^4 \cdot 15 \cdot 101 \approx 4{,}5 \cdot 10^7$. Mỗi phương án được giải đúng một lần (ở đoạn nhỏ nhất chứa nó mà nó đi qua điểm chia) với $O(c)$ phép tính, tổng $O(Q \cdot c)$. Ta chỉ cần bảng cho các bến của đoạn đang xét, nên dùng chung một mảng $F$ cỡ $N \cdot (c + 1)$ cho mọi đoạn.
Nhóm bên trái là $r \le mid$ (có dấu bằng). Nếu viết $r < mid$, phương án kết thúc đúng tại $mid$ bị đưa vào nhóm "đi qua điểm chia" và lấy nhầm $F[mid]$ — bảng của nửa trái — làm nửa phải, kiện ở bến $mid$ bị tính hai lần. Lỗi này vẫn qua được ví dụ của đề nhưng chỉ được khoảng một phần tư số điểm.
Để không phải đệ quy (Python dễ tràn ngăn xếp), mình dùng một ngăn xếp chứa các bộ $(lo, hi, \text{danh sách phương án})$: lấy ra một đoạn, chia nhóm, giải nhóm đi qua điểm chia, rồi đẩy hai đoạn con (nếu còn phương án) vào ngăn xếp. Thứ tự xử lý các đoạn không quan trọng vì mỗi phương án chỉ được giải một lần.
Code chuẩn: mảng phẳng F dài $(N + 2)(W + 1)$ với $W = \max c_j$; bến $i$ dùng đoạn F[i*(W+1) .. i*(W+1)+W]. Bản Python giữ đúng cấu trúc (ngăn xếp, ba nhóm, mảng F theo bến) nhưng mỗi lần "thêm kiện" tạo danh sách mới bằng map(max, ...) và phép ghép dùng max(map(add, ...)) để chạy nhanh.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, q, W;
vector<int> w, l, r, c;
vector<ll> v, ans, F; // F: mảng QHĐ của mọi bến, bến i dùng F[i*(W+1) .. i*(W+1)+W]
// dst = src + thêm kiện vở của bến i (cái túi 0/1, "tổng khối lượng <= x")
void addItem(const ll *src, ll *dst, int i) {
for (int x = 0; x <= W; x++) dst[x] = src[x];
for (int x = w[i]; x <= W; x++) dst[x] = max(dst[x], src[x - w[i]] + v[i]);
}
int main() {
scanf("%d %d", &n, &q);
w.resize(n + 2); v.resize(n + 2);
for (int i = 1; i <= n; i++) scanf("%d %lld", &w[i], &v[i]);
l.resize(q); r.resize(q); c.resize(q); ans.assign(q, 0);
W = 0;
for (int j = 0; j < q; j++) { scanf("%d %d %d", &l[j], &r[j], &c[j]); W = max(W, c[j]); }
F.assign((size_t)(n + 2) * (W + 1), 0);
vector<ll> zero(W + 1, 0);
// chia để trị không đệ quy: mỗi phần tử ngăn xếp là đoạn [lo, hi] và các phương án nằm gọn trong đoạn
vector<int> all;
for (int j = 0; j < q; j++) {
if (l[j] == r[j]) ans[j] = (w[l[j]] <= c[j]) ? v[l[j]] : 0;
else all.push_back(j);
}
vector<tuple<int, int, vector<int>>> st;
st.emplace_back(1, n, all);
while (!st.empty()) {
auto [lo, hi, qs] = move(st.back());
st.pop_back();
if (qs.empty()) continue;
int mid = (lo + hi) / 2;
vector<int> qa, qb, cross;
for (int j : qs) {
if (r[j] <= mid) qa.push_back(j);
else if (l[j] > mid) qb.push_back(j);
else cross.push_back(j);
}
if (!cross.empty()) {
int mn = mid, mx = mid + 1;
for (int j : cross) { mn = min(mn, l[j]); mx = max(mx, r[j]); }
// F[i] (i <= mid): các kiện từ bến i tới bến mid; F[i] (i > mid): các kiện từ bến mid+1 tới bến i
addItem(zero.data(), &F[(size_t)mid * (W + 1)], mid);
for (int i = mid - 1; i >= mn; i--) addItem(&F[(size_t)(i + 1) * (W + 1)], &F[(size_t)i * (W + 1)], i);
addItem(zero.data(), &F[(size_t)(mid + 1) * (W + 1)], mid + 1);
for (int i = mid + 2; i <= mx; i++) addItem(&F[(size_t)(i - 1) * (W + 1)], &F[(size_t)i * (W + 1)], i);
for (int j : cross) {
const ll *A = &F[(size_t)l[j] * (W + 1)], *B = &F[(size_t)r[j] * (W + 1)];
ll best = 0;
for (int x = 0; x <= c[j]; x++) best = max(best, A[x] + B[c[j] - x]); // ghép hai nửa
ans[j] = best;
}
}
if (!qa.empty()) st.emplace_back(lo, mid, move(qa));
if (!qb.empty()) st.emplace_back(mid + 1, hi, move(qb));
}
string out;
for (int j = 0; j < q; j++) { out += to_string(ans[j]); out += '\n'; }
fputs(out.c_str(), stdout);
return 0;
}import sys
from operator import add
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
w = [0] * (n + 2); v = [0] * (n + 2)
p = 2
for i in range(1, n + 1):
w[i] = int(data[p]); v[i] = int(data[p + 1]); p += 2
L = [0] * q; R = [0] * q; C = [0] * q
for j in range(q):
L[j] = int(data[p]); R[j] = int(data[p + 1]); C[j] = int(data[p + 2]); p += 3
W = max(C)
ans = [0] * q
zero = [0] * (W + 1)
F = [zero] * (n + 2) # F[i]: mảng QHĐ "khối lượng <= x" của bến i (như bản C++)
allq = []
for j in range(q):
if L[j] == R[j]:
ans[j] = v[L[j]] if w[L[j]] <= C[j] else 0
else:
allq.append(j)
st = [(1, n, allq)] # chia để trị bằng ngăn xếp, không đệ quy
while st:
lo, hi, qs = st.pop()
mid = (lo + hi) // 2
qa = [j for j in qs if R[j] <= mid]
qb = [j for j in qs if L[j] > mid]
cross = [j for j in qs if L[j] <= mid < R[j]]
if cross:
mn = min([L[j] for j in cross]); mx = max([R[j] for j in cross])
prev = zero
for i in range(mid, mn - 1, -1): # F[i]: các kiện từ bến i tới bến mid
wi = w[i]
if wi <= W:
vi = v[i]
prev = prev[:wi] + list(map(max, prev[wi:], map(vi.__add__, prev)))
F[i] = prev
prev = zero
for i in range(mid + 1, mx + 1): # F[i]: các kiện từ bến mid + 1 tới bến i
wi = w[i]
if wi <= W:
vi = v[i]
prev = prev[:wi] + list(map(max, prev[wi:], map(vi.__add__, prev)))
F[i] = prev
for j in cross: # ghép hai nửa: max của A[x] + B[c - x]
c = C[j]
ans[j] = max(map(add, F[L[j]][:c + 1], F[R[j]][c::-1]))
if qa:
st.append((lo, mid, qa))
if qb:
st.append((mid + 1, hi, qb))
sys.stdout.write("\n".join(map(str, ans)) + "\n")
main()Mỗi kiện nặng ít nhất $1$ kg nên một phương án nhận tối đa $100$ kiện, tổng tới $100 \cdot 10^9 = 10^{11}$ quyển — vượt int, phải dùng long long.
Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 | Sub 2 | Sub 3 | Sub 4 | Sub 5 | Điểm |
|---|---|---|---|---|---|---|
| Cách 1 – cái túi cho từng phương án | Đúng | TLE | TLE | TLE | TLE | 10 |
| Cách 2 – bảng tiền tố (chỉ đúng khi l = 1) | 0/7 | Đúng | 0/7 | 0/8 | 0/10 | 15 |
| Cách 3 – gom theo l, quét r | Đúng | Đúng | Đúng | TLE | TLE | 45 |
| Cách 4 – ghép hai nửa tại bến m | 0/7 | 0/7 | 0/7 | Đúng | 0/10 | 25 |
| Cách 5 – chia để trị (lời giải chuẩn) | Đúng | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: viết $r < mid$ thay cho $r \le mid$ | 4/7 | 2/7 | 0/7 | 5/8 | 0/10 | 25,62 |
Sai: dùng int | 4/7 | 4/7 | 3/7 | 2/8 | 4/10 | 41,11 |
| Sai: QHĐ "khối lượng đúng bằng x" | 1/7 | 0/7 | 0/7 | 2/8 | 0/10 | 7,68 |
| Sai: cập nhật trên chính bảng mới (một kiện lấy nhiều lần) | 1/7 | 0/7 | 0/7 | 0/8 | 0/10 | 1,43 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: 39 test (subtask 1: 7 test, subtask 2: 7 test, subtask 3: 7 test, subtask 4: 8 test, subtask 5: 10 test), chấm kiểu "đúng test nào được điểm test đó". Mọi test của subtask 2, 4, 5 có $N$ xấp xỉ $3 \cdot 10^4$ và $Q = 5 \cdot 10^4$; subtask 3 có $N = 3000$, $Q = 5 \cdot 10^4$ với phần lớn phương án dài gần hết dãy bến (để Cách 1 không qua được). Kiện vở có loại rất nhẹ ($1$–$5$ kg, mỗi phương án nhận cả trăm kiện), rất nặng, trộn lẫn, số vở tới $10^9$ (vượt int) hoặc gần tỉ lệ với khối lượng (khó cho tham lam). Subtask 4 có test mà kiện ở bến $m$ rất nhẹ, nhiều vở, và nhiều phương án kết thúc hoặc bắt đầu đúng tại bến $m$. Subtask 5 trộn phương án dài, ngắn (vài chục bến), cực ngắn và phương án chỉ một bến. Lời giải chuẩn C++ chạy dưới 0,3 giây. Bản Python nên nộp bằng PyPy 3 (giới hạn 4 giây).
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét