200 200000
1 1 1000000000
1 2 -1
1 3 1000000000
1 4 -1
1 5 1000000000
1 6 1000000000
1 7 1000
<2708 bytes omitted>用户输出
40000000系统信息
Exited with return code 0| 编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
|---|---|---|---|---|---|---|---|---|
| #68994 | #1206. Day4D. ZJY 沉迷群星的原因 | Accepted | 100 | 473 ms | 1980 K | C++ 11 / 1.1 K | 该起什么名字 | 2022-04-23 13:54:22 |
#include <bits/stdc++.h>
#define F(i, n, m) for (int i = n; i <= m; i++)
#define f(i, n, m) for (int i = n; i >= m; i--)
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
inline ll read() {
ll num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r')
;
if (c == '-')
flag = true;
else
num = c - '0';
while (isdigit(c = getchar())) num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
ll w[200005], v[200005], k[200005];
ll dp[200005];
int n, m;
void manyPack(int i);
void infPack(int i);
int main() {
std::ios::sync_with_stdio(false);
n = read();
m = read();
F(i, 1, n) {
w[i] = read();
v[i] = read();
k[i] = read();
}
dp[0] = 0;
F(i, 1, n) {
if (k[i] == -1)
infPack(i);
else {
ll dig = k[i], tmp;
for (ll ww = 1; dig > 0; ww <<= 1) {
tmp = min(ww, dig);
for (ll j = m; j >= tmp * w[i]; j--) {
dp[j] = max(dp[j], dp[j - tmp * w[i]] + 1ll * tmp * v[i]);
}
dig -= ww;
}
}
}
cout << dp[m];
return 0;
}
void infPack(int i) { F(j, w[i], m) dp[j] = max(dp[j], dp[j - w[i]] + v[i]); }
200 200000
1 1 1000000000
1 2 -1
1 3 1000000000
1 4 -1
1 5 1000000000
1 6 1000000000
1 7 1000
<2708 bytes omitted>用户输出
40000000系统信息
Exited with return code 0用户输出
676022593系统信息
Exited with return code 0154 5656
2089 656841374 331742632
4436 895510988 -1
670 568657720 491720332
94967 798516351 -1
<3218 bytes omitted>用户输出
20700931032系统信息
Exited with return code 039 33432
52774 165018658 463715299
195594 576500509 -1
16793 123305761 776456693
568 281193514 -
<775 bytes omitted>用户输出
65334130576系统信息
Exited with return code 0用户输出
2026182552系统信息
Exited with return code 0103 130077
89500 400633235 393817025
60693 624669715 -1
70725 120321529 -1
62535 347835332 10812
<2266 bytes omitted>用户输出
31429720980系统信息
Exited with return code 014 108109
150845 352561944 -1
99633 252473099 -1
48061 305926012 -1
84645 844295694 -1
56953 54
<221 bytes omitted>用户输出
7543809362系统信息
Exited with return code 0162 95933
86019 785153299 -1
128609 875546751 240184754
8653 250318660 -1
77825 883182325 -1
10
<3572 bytes omitted>用户输出
41407574578系统信息
Exited with return code 0用户输出
527005142系统信息
Exited with return code 0116 128046
124080 970724936 824179885
182162 712567029 442305830
146447 613366582 336706287
4714
<2579 bytes omitted>用户输出
65633464200系统信息
Exited with return code 0200 42412
163986 705209262 -1
6966 961317127 827519246
70539 540666196 -1
26909 349604372 -1
18
<4256 bytes omitted>用户输出
95353238340系统信息
Exited with return code 0200 76217
134431 367278856 932429320
54256 832955080 -1
88279 250194105 543823452
59329 68484867
<4371 bytes omitted>用户输出
66970203733系统信息
Exited with return code 0200 147878
20724 840729052 -1
176087 756691368 884829082
31785 781703356 -1
79010 432462491 -1
<4433 bytes omitted>用户输出
485613273312系统信息
Exited with return code 0200 184712
127063 895415122 -1
29535 543755380 -1
168413 109463521 -1
50489 76721663 -1
93862 5
<4420 bytes omitted>用户输出
202169905756系统信息
Exited with return code 0200 73815
83089 576924208 991545530
184450 527382467 -1
68516 155321877 -1
49801 170761297 -1
1
<4380 bytes omitted>用户输出
149225128606系统信息
Exited with return code 043 35202
59405 714153602 259411327
10246 448827780 374317677
36594 460806556 -1
58824 1924657 56
<876 bytes omitted>用户输出
228201085014系统信息
Exited with return code 0