# THI THỬ HSG TỈNH K9 - 2025 - I

>[!Note] Thông tin
>**Thời gian:** 21:00 - 23:30 ngày 24/02/2025
>**Contest:** [TẠI ĐÂY](https://chuyentinbrvt.online/contest/algi_mockhsg9lan1_2025)
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Triển lãm (5 điểm)

### Tóm tắt đề bài:

Tại một triển lãm nghệ thuật, có $n$ phòng trưng bày xếp thành một vòng tròn, được đánh số từ $1$ đến $n$. Mỗi phòng cần có chính xác $R_i$ khách tham quan. Chỉ được mở cửa **một phòng duy nhất** để khách tiến vào, sau đó đi đến các phòng khác **theo chiều kim đồng hồ**.

**Yêu cầu:** Tìm căn phòng mà anh Tèo cần mở cửa vào để tổng khoảng cách di chuyển của các vị khách là nhỏ nhất. Nếu có nhiều hơn một căn phòng như vậy, tìm căn phòng có số hiẹu nhỏ nhất

**Dữ liệu bảo đảm:** $1 \le n \le 10^6; 1 \le R_i \le 10^4$

**Subtasks:**
- $20\%$ số điểm: $1 \le n \le 100$.
- $40\%$ số điểm: $100 \lt n \le 10^3$.
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1:

Thử chọn từng căn phòng $i$ để mở cửa, sau đó duyệt qua tất cả những phòng $j$ còn lại và tính tổng khoảng cách để $R_j$ vị khách có thể đến được căn phòng $j$ bằng một vòng lặp.

**Độ phức tạp thời gian:** $O \left( n^3 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int n, resPos, R[N+1];
long long resVal = LLONG_MAX;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> R[i];
	}

	for (int i = 1; i <= n; i++) {
		long long sum = 0;
		for (int j = 1; j <= n; j++) {
			int step = 0, dup = j;
			while (dup != i) {
				dup--;
				step++;

				if (dup < 1) {
					dup = n;
				}
			}

			sum += (long long)step * R[j];
		}

		if (resVal > sum) {
			resVal = sum;
			resPos = i;
		} else if (resVal == sum) {
			resPos = min(resPos, i);
		}
	}

	cout << resPos << " " << resVal;

	return 0;
}

:::

### Subtask 2:

Ý tưởng tương tự với subtask trước, nhưng cải tiến bước ==tính tổng khoảng cách== để $R_j$ vị khách có thể đến được căn phòng $j$ bằng cách sử dụng công thức:
- $j-i$ nếu $j \gt i$.
- $n - \left( i - j \right)$ nếu $j \lt i$.

**Độ phức tạp thời gian:** $O \left( n ^ 2 \right)$

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;
int n, resPos;
long long resVal = LLONG_MAX, R[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> R[i];
	}

	for (int i = 1; i <= n; i++) {
		long long sum = 0;
		for (int j = 1; j <= n; j++) {
			if (j >= i) {
				sum += (j - i) * R[j];
			} else {
				sum += (n - (i - j)) * R[j];
			}
		}

		if (resVal > sum) {
			resVal = sum;
			resPos = i;
		} else if (resVal == sum) {
			resPos = min(resPos, i);
		}
	}

	cout << resPos << " " << resVal;

	return 0;
}

:::

### Subtask 3:

>[!Tip] Quan sát và nhận xét
> Giả sử ta mở cửa phòng $i$, ta có khoảng cách để đến các phòng còn lại như sau:
> 
> $$
> \left( 1 \cdot R_{i+1} \right) + \left( 2 \cdot R_{i+2} \right) + \left( 3 \cdot R_{i+3} \right) + \dots + \left[ \left( n-1 \right) \cdot R_{i-1} \right]
> $$
> Vẫn lấy ==điểm $i$ làm mốc==, khi ta mở cửa ở phòng $i+1$, dễ thấy biểu thức tính khoảng cách thay đổi thành:
> $$
> \left( 0 \cdot R_{i+1} \right) + \left( 1 \cdot R_{i+2} \right) + \left( 2 \cdot R_{i+3} \right) + \dots + \left[ \left( n-1 \right) \cdot R_i \right]
> $$

Khi ta thay đổi việc mở cửa ở phòng hiện tại (tạm gọi là $x$), để mở phòng tiếp theo theo chiều kim đồng hồ (tạm gọi là $y$):
- Khoảng cách để đến ==tất cả các phòng (trừ phòng $x$)== đều giảm đi $1$.
- Cộng thêm khoảng cách để đến ==phòng $x$== là $\left( n - 1 \right) \cdot R_x$.

Như vậy, để giải bài toán trên, ta tính trước đáp án nếu mở cửa ở phòng $1$. Sau đó duyệt đến $n$ và thay đổi đáp án ở từng bước duyệt như đã giải thích ở trên.

**Độ phức tạp thời gian:** $O \left (n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int n;
long long R[N+1], PF[N+1], SF[N+1];

int32_t main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> R[i];
		PF[i] = PF[i-1] + R[i];
	}

	SF[n] = R[n];
	for (int i = n-1; i >= 1; i--) {
		SF[i] = SF[i+1] + R[i];
	}

	long long sum = 0;
	for (int i = 2; i <= n; i++)
		sum += (i - 1) * R[i];

	int resPos = 1, resVal = sum;
	for (int i = 2; i <= n; i++) {
		sum -= SF[i] + PF[i-2];
		sum += R[i-1] * (n - 1);

		if (resVal > sum) {
			resVal = sum;
			resPos = i;
		} else if (resVal == sum) {
			resPos = min(resPos, i);
		}
	}

	cout << resPos << " " << resVal;

	return 0;
}

:::

## Bài 2: Trò chơi giai thừa (5 điểm)

### Tóm tắt đề bài:

Tí tấn công Quái Vật Giai thừa $t$ lần. Vào lần thứ $i$, Tí cần tìm số nguyên không âm $x$ lớn nhất để dựng lên một hàng rào phép thuật có sức mạnh $k^x$ sao cho $k^x$ là ước của $n!$

Giải thích: $n! = 1 \cdot 2 \cdot 3 \dots n$

**Mô hình hóa bài toán:** Cho $t$ truy vấn và giá trị $n$, mỗi truy vấn cho $k$, tìm số nguyên không âm $x$ lớn nhất thỏa $n! \bmod k^x = 0$

**Dữ liệu bảo đảm:** $1 \le t \le 10^5; 1 \le n \le 10^{18}; 2 \le k_i \le 10^6$.

**Subtasks:**
- $20\%$ số điểm: $t = 1; 1 \le n \le 15; 2 \le k_i \le 10$
- $40\%$ số điểm: $t = 1; 1 \le n \le 10^4; 2 \le k_i \le 10^6$
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1:

Vì $n \le 15$, do đó $n!$ tối đa có thể đạt đến khoảng $10^{12}$, có thể lưu trữ được trong kiểu dữ liệu **long long**.

Như vậy, ta ==tính $n!$ và duyệt $x$ tăng dần== để tìm đáp án.

**Độ phức tạp thời gian:** $O \left( n + \log_k n!\right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

long long n, t, k;

int main() {
    cin >> n >> t >> k;

    long long fact = 1;
    for (int i = 1; i <= n; i++)
        fact *= i;

    long long pw = 0, val = 1;
    while (fact % val == 0) {
        pw++;
        val *= k;
    }

    cout << pw - 1;

    return 0;
}

:::

### Subtask 2:

Với $n \le 10^4$, việc tính $n!$ trực tiếp như subtask trước là không khả thi.

>[!Tip] Kiến thức toán học cần biết
> Giả sử $a = p_1^{x_1} \cdot p_2^{x_2} \cdot p_3^{x_3} \dots \cdot p_k^{x_k}$ với $p_1, p_2, \dots, p_k$ là các thừa số nguyên tố của $a$.
> Khi đó, ==một số $b$ chia hết cho $a$== khi và chỉ khi với mọi thừa số nguyên tố $p_i^{x_i}$ của $a$ thì số $b$ cũng nhận $p_j^{x_j}$ làm thừa số nguyên tố trong đó $x_j \ge x_i$.
> > **Ví dụ, xét:**
> > $a = 10 = 2^1 \cdot 5^1$
> > $b = 200 = 2^3 \cdot 5^2$
> >
> > $b$ chia hết cho $a$ vì:
> > - Với thừa số nguyên tố $2$, khi phân tích số $a$ và $b$ ta được số mũ $3 \gt 2$.
> > - Với thừa số nguyên tố $5$, khi phân tích số $a$ và $b$ ta được số mũ $2 \gt 1$

Lưu $cnt_i$ là số mũ của thừa số nguyên tố $i$ trong phân tích thừa số nguyên tốt của $n!$

Xét $n! = 1 \cdot 2 \cdot 3 \dots n$, có thể phân tích thừa số nguyên tố $n!$ bằng cách duyệt qua mọi số $x$ từ $1$ đến $n$ và phân tích thừa số nguyên tố của $x$. Sau đó phân tích thừa số nguyên tố của $k$.

Cuối cùng, ta xét mọi thừa số nguyên tố $p$ của $k$, gọi:
- $x$ là số mũ của $p$ trong phân tích thừa số nguyên tố của $k$
- $y$ là số mũ của $p$ trong phân tích thừa số nguyên tố của $n!$

**Kết quả:** Giá trị nhỏ nhất của $\left \lfloor \frac{y}{x} \right \rfloor$.

**Độ phức tạp thời gian:** $O \left( \sum_{i = 1}^n \sqrt i \right)$.
> Tổng $\sqrt i$ với $i$ từ $1$ đến $n$ (phân tích thừa số nguyên tố của $n!$).

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int V = 1e6;
long long n, t, k, res = LLONG_MAX, cnt[V+1];

int main() {
    cin >> n >> t >> k;

    for (int i = 2; i <= n; i++) {
        int p = 2, dup = i;

        while (p*p <= dup) {
            while (dup % p == 0) {
                cnt[p]++;
                dup /= p;
            }

            p++;
        }

        if (dup > 1) {
            cnt[dup]++;
        }
    }

    long long p = 2;
    while (p*p <= k) {
        int cur = 0;
        while (k % p == 0) {
            k /= p;
            cur++;
        }

        if (cur) res = min(res, cnt[p] / cur);
        p++;
    }

    if (k > 1) {
        res = min(res, cnt[k]);
    }

    cout << res;

    return 0;
}

:::

### Subtask 3:

Ý tưởng kế thừa từ subtask trước, tuy nhiên cần cải tiến khâu phân tích thừa số nguyên tố của $n!$ và khâu phân tích thừa số nguyên tố của $k_i$

#### Phân tích thừa số nguyên tố của $n!$

>[!Important] Quan sát và nhận xét
>Xét $10! = 1 \cdot 2 \cdot 3 \dots n$ và số nguyên tố $p = 2$. Từ $1$ đến $n$ có:
>- $2 = 2^1$.
>- $4 = 2^2$.
>- $6 = 2 \cdot 3$.
>- $8 = 2^3$.
>- $10 = 2 \cdot 5$
>
> Khi đó ta nói $10!$ có:
> - $5$ số $2$ bậc $1$ ở $2, 4, 6, 8, 10$.
> - $2$ số $2$ bậc $2$ ở $4, 8$.
> - $1$ số $2$ bậc $3$ ở $8$.

Như vậy, có thể tính nhanh số mũ $x$ của một số nguyên tố $p$ bất kỳ trong phân tích thừa số nguyên tố của $n!$ bằng cách:
- Tính số lượng số $p$ xuất hiện ở bậc $1$.
- Tính số lượng số $p$ xuất hiện ở bậc $2$.
- $\dots$

Và tính tổng số lượng số $p$ ở ==tất cả các bậc==.

>[!Tip] Công thức
> Số lượng thừa số nguyên tố $p$ bậc $k$ trong phân tích thừa số nguyên tố của $n$ là:
> $$
> \left \lfloor \frac{n}{p^k} \right \rfloor
> $$

#### Phân tích thừa số nguyên tố của $k_i$

Nhận thấy trong subtask này, số lượng $k_i$ lớn, lên đến $10^5$, do đó cần một thuật toán để phân tích thừa số nguyên tố số $k_i$ trong $\log k_i$.

Một cách đó là ==sàng ước nguyên tố==. Ở đây, lưu $E_i$ là thừa số nguyên tố nhỏ nhất của $i$. Khi đó, ta có thể phân tích số $x$ bất kì thành thừa số nguyên tố trong $O \left( \log x \right)$ vì:
- Mảng $E$ cho phép ==truy cập ngay== tới thừa số nguyên tố của $x$.
- Một số $x$ bất kì chỉ có thể phân tích thành ==tối đa $\log$ thừa số nguyên tố== vì số nguyên tố nhỏ nhất là $2$.

>[!Tip]
> Cách xây dựng mảng $E$ dựa trên **sàng số nguyên tố Erastosthenes**.
>
> Ta duyệt $i$ từ $2$ đến giá trị tối đa, nếu $E_i$ với $i$ là số nguyên tốt chưa được gán giá trị, chắc chắn $i$ và bội của $i$ sẽ nhận $i$ là thừa số nguyên tốt nhỏ nhất.
>
> Giả sử ta sàng tới $N$, độ phức tạp thời gian là $O \left( N \log N\right)$.

**Độ phức tạp thời gian:**
$$
O \left(\log k_1 + \log k_2 + \dots + \log k_t + \log n! \right) = O \left( \sum_{i = 1}^t \log k_i + \log n! \right)
$$

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int T = 1e5, V = 1e6;
long long res, t, n, k, E[V+1];

void sieve() {
    for (int i = 2; i <= V; i++) {
        if (!E[i]) {
            for (int j = i; j <= V; j += i) {
                E[j] = i;
            }
        }
    }
}

long long calc(long long p) {
    long long ret = 0, dup = n;

    while (dup /= p)
    ret += dup;

    return ret;
}

void factorize(long long num) {
    while (num > 1) {
        long long p = E[num], cnt = 0;

        while (num % p == 0) {
            num /= p;
            cnt++;
        }

        long long req = calc(p);
        res = min(res, req / cnt);
    }
}

int main() {
    sieve();

    cin >> n >> t;
    while (t--) {
        cin >> k;

        res = LLONG_MAX;
        factorize(k);

        cout << res << " ";
    }

    return 0;
}

:::

## Bài 3: Cắt bánh (5 điểm)

### Tóm tắt đề bài:

Có một chiếc bánh đã được chia sẵn thành $a$ phần đều nhau. Tiếp tục chia **tất cả các phần bánh đó ra**, mỗi phần thành $a$ phần nhỏ hơn, tổng cộng $b$ lần. Chia đều số lượng phần bánh cho $c$ thực khách, sẽ có một lượng bánh dư ra là $x$.

**Yêu cầu:** Tính $x$.

**Mô hình hóa bài toán:** Sau $b$ lần cắt, ta được số phần bánh là:
$$
\underbrace{a \cdot a \cdot a \dots a}_{b} = a^b
$$

Bài toán yêu cầu tính $a^b \bmod c$.

**Dữ liệu bảo đảm:** $1 \le a, b, c \le 10^{18}$.

**Subtasks:**
- $20\%$ số điểm: $a, b \le 10^6, \; c \le 10^9$.
- $40\%$ số điểm: $a, b \le 10^{18}, \; c \le 10^{9}$.
- $40\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1:

Vì $b \le 10^6$, có thể tính đáp án bằng cách duyệt và nhân thêm $a$ vào kết quả $b$ lần.
>[!caution]
> **Lưu ý:** Kết quả của phép tính trên là rất lớn, do đó cần lồng phép tính chia dư vào quá trình tính đáp án, chứ không thể tính xong rồi mới chia dư cho $c$. Ta có tính chất
> :::warning
> $$
> \left( a \cdot b \right) \bmod c = \left[ \left( a \bmod c \right) \cdot \left( b \bmod c \right) \right] \bmod c
> $$
> :::

**Độ phức tạp thời gian:** $O \left( b \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

long long a , b , c , ans;

int main() {
    cin >> a >> b >> c;
    
    ans = 1;
    for(int i = 1; i <= b; i++)
        ans = ((ans % c * (a % c)) % c;
    
    cout << ans;

    return 0;
}

:::

### Subtask 2:

Với $b$ lên đến $10^{18}$, thí sinh bắt buộc phải sử dụng thuật toán kinh điển liên quan tới lũy thừa, đó là **[lũy thừa nhị phân](https://wiki.vnoi.info/algo/algebra/binary_exponentation.md)**.

**Độ phức tạp thời gian:** $O \left( \log b\right)$

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

long long a , b , c , ans;

long long mul (long long a, long long b) {
    a %= c;
    b %= c;
    return (a * b) % c;
}

long long mod_pow(long long a, long long b, long long c) {
    if (b == 0) {
        return 1;
    }
        
    long long X = mod_pow(a, b / 2, c);

    if (b % 2 == 1) {
        return mul(X, mul(X, a));
    }
    
    return mul(X, X);
}

int main() {
    cin >> a >> b >> c;
    
    ans = solve(a, b, c);
    cout << mod_pow(a, b, c);

    return 0;
}

:::

### Subtask 3:

>[!Warning] Chú ý
> Giới hạn $c \le 10^{18}$ đồng nghĩa với việc, trong bất kỳ phép tính nào, các giá trị luôn có thể lên đến $10^{18}$ vì:
> $$
> x \bmod c \le c
> $$

Trong thuật toán lũy thừa nhị phân, cốt lõi là chia một lũy thừa ra làm hai nửa và nhân lại với nhau. Vì vẫn còn tồn tại phép nhân, phép tính có thể trả về một số lên đến $10^{36}$, hoàn toàn vượt ngoài phạm vi của **long long**.

>[!Tip]
> Có thể áp dụng tư tưởng chia để trị như với phép lũy thừa
> :::success
> - Ở phép **lũy thừa**, có thể giảm trừ thành phép **nhân** vì:
> $$
> a^x = a^{\frac x 2} \cdot a^{\frac x 2}
> $$
> - Ở phép **nhân**, có thể giảm trừ thành phép **cộng** vì:
> $$
> a \cdot b = a \cdot \frac b 2 + a \cdot \frac b 2
> $$
> :::

**Độ phức tạp thời gian:** $O \left( \log^2 b \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

long long a, b, c, ans;

long long mul(long long x, long long y) {
    x %= c;
    y %= c;
    return (x * y) % c;
}

long long add(long long x, long long y) {
    x %= c;
    y %= c;
    return (x + y) % c;
}

long long calc(long long a, long long b) {
    if (b == 0) {
        return 0;
    }
    
    long long hf = calc(a, b/2);
    
    if (b & 1)
        return add(add(hf, hf), a);
    else
        return add(hf, hf);
}

long long solve(long long a, long long b)
{   
    if (b == 0) return 1;
    if (b == 1) return a % c;
    
    ll hf = solve(a, b/2);
    
    if (b % 2 == 1) {
        return calc(calc(hf, hf), a);
    } else {
        return calc(hf, hf);
    }
}

int main() {
    cin >> a >> b >> c;

    ans = solve(a, b);
    cout << ans;

    return 0;
}

:::

## Bài 4: Balo chịu lực (5 điểm)

### Tóm tắt đề bài:

Khoa đang thực hiện chuyển nhà và anh sẽ đặt các món đồ của mình vào một chiếc balo với sức chứa $S$. Nếu bỏ quá nhiều đồ vào ba lô, khiến tổng trọng lượng đạt tới $T \gt S$ thì ba lô vẫn có thể chứa được, nhưng các món đồ bên trong sẽ phải chịu một áp lực do quá tải, ==chính xác là $T - S$==.

Khoa có $n$ món đồ, ==món đồ thứ $i$ có khối lượng $a_i$, giá trị $b_i$, nhưng chỉ có thể chịu được một mức áp lực tối đa là $p_i$==. Nếu áp lực trong ba lô lớn hơn khả năng chịu đựng của món đồ nào đó, nó sẽ bị hỏng!

**Yêu cầu:** Tìm cách để Khoa lấy được tổng giá trị lớn nhất mà vẫn đảm bảo không món đồ nào bị hỏng.

**Dữ liệu bảo đảm:**
- $1 \le n \le 100$
- $1 \le S, a_i, p_i \le 10^5$
- $1 \le b_i \le 10^9$

**Subtasks:**
- $25\%$ số điểm: $1 \le n \le 15$.
- $25\%$ số điểm: $1 \le p_i \le 100; 1$.
- $50\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1:

Quay lui thử tất cả các cách chọn.

**Độ phức tạp thời gian:** $O \left( 2^n \right)$.

### Subtask 2:

Cố định mức áp lực mà balo phải chịu là $P$, dễ thấy chỉ có thể bỏ các món đồ với $p_i \le P$ vào balo.

Như vậy, với $P$ từ $1$ đến $\max(p_i)$, bài toán trở thành bài toán quy hoạch động điển hình:

:::info
Bỏ một số vật phẩm vào balo với ==giới hạn khối lượng là $S + P$== sao cho tổng giá trị là lớn nhất có thể.
:::

Đặt trạng thái $dp_{i, j}$ là tổng giá trị lớn nhất có thể lấy được khi xét $i$ món đồ đầu tiên, với tổng khối lượng là $j$.

Có hai trường hợp chuyển trạng thái như sau:
- $dp_{i, j} = dp_{i-1, j}$: Không lấy món đồ $i$.
- $dp_{i, j} = dp_{i-1, j-a_i} + b_i$: Lấy món đồ $i$.

Giải bài toán trên với mọi giá trị $P$, sau đó lấy đáp án lớn nhất, đó chính là kết quả của bài toán chung.

**Độ phức tạp thời gian:** $O \left( P \cdot n \cdot S \right)$ với $P = \max(p_i)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 100, mxP = 100, mxS = 1e4;
long long n, S, res, V[N+1], C[N+1], P[N+1], dp[N+1][mxS + mxP + 1];

int main() {
	cin >> n >> S;
	for (int i = 1; i <= n; i++) {
		cin >> V[i] >> C[i] >> P[i];
	}

	for (int p = 0; p <= mxP; p++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= S + p; j++) {
				dp[i][j] = dp[i-1][j];
				if (P[i] >= p && j >= V[i]) {
					dp[i][j] = max(dp[i][j], dp[i-1][j - V[i]] + C[i]);
                }
            }
        }

		res = max(res, dp[n][S + p]);
	}

	cout << res;

	return 0;
}

:::

### Subtask 3:

Vấn đề cốt lõi của bài toán này vẫn là việc áp lực của balo bất định. Nếu giải quyết được vấn đề này, bài toán sẽ được đơn giản hóa thành bài toán điển hình.

Cách làm ở subtask trước là không khả thi khi giới hạn dữ liệu lớn.

Cách làm tối ưu là ==sort lại các món đồ theo $p_i$ giảm dần==. Khi đó, xét đến món đồ thứ $i$, rõ ràng $p_i$ là nhỏ nhất trong $i$ món đồ đầu tiên, do đó tất cả $i$ vật này đều có thể chịu được áp lực lên đến $p_i$,. Nghĩa là trong trạng thái $dp_{i, j}$ có thể duyệt $j$ từ $0$ đến $S + p_i$.

**Độ phức tạp thời gian:** $O \left( n S \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e2 + 5, M = 2e5 + 5;
int n, s, a[N], b[N], p[N], x[N];
long long weight, value, ans, sum, dp[N][M], pressure_max;

struct dynamic{
    long long w, v, pr;
} balo[N];

void sub3()
{
    for(int i = 1; i <= n; i++)
        balo[i].w = a[i],
        balo[i].v = b[i],
        balo[i].pr = p[i];

    sort(balo + 1, balo + 1 + n, [&] (dynamic a, dynamic b) {
        return a.pr > b.pr;
    });

    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <=  s + pressure_max; j++) {
            dp[i][j] = (j - balo[i].w >= 0 && j <= s + balo[i].pr ? max(dp[i - 1][j], dp[i - 1][j - balo[i].w] + balo[i].v) : dp[i - 1][j]);
        }
    }

    for(int i = 0; i <= s + pressure_max; i++)
        ans = max(ans, dp[n][i]);

    cout << ans;
}

int main() {
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> p[i];
        pressure_max = max(pressure_max, (long long)p[i]);
    }

    sub3();
    return 0;
}

:::