QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#536120 | #5303. No Bug No Game | ucup-team1329# | WA | 59ms | 144344kb | C++20 | 1.4kb | 2024-08-28 18:46:39 | 2024-08-28 18:46:39 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using A2 = std::array<i64, 2>;
#define Fast_IOS std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
const i64 mod = 998244353;
i64 MAX(i64 &a, i64 b) {
return a = std::max(a, b);
}
class WORK {
public:
int N;
WORK() {}
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<i64> w(n + 1);
std::vector val(n + 1, std::vector<i64>());
for (int i = 1; i <= n; i++) {
std::cin >> w[i];
val[i].push_back(0);
for (int j = 1; j <= w[i]; j++) {
i64 x;
std::cin >> x;
val[i].push_back(x);
}
}
std::vector f(n + 1, std::vector<A2>(m + 1));
for (int i = 1; i <= n; i++) {
for (int k = m; k >= 0; k--) {
f[i][k][0] = f[i - 1][k][0];
f[i][k][1] = f[i - 1][k][1];
}
for (int j = 1; j <= w[i] - 1; j++) {
for (int k = m; k >= j; k--) {
MAX(f[i][k][1], std::max(f[i - 1][k - j][0], f[i - 1][k - j][1]) + val[i][j]);
}
}
for (int k = m; k >= w[i]; k--) {
MAX(f[i][k][0], f[i - 1][k - w[i]][0] + val[i][w[i]]);
MAX(f[i][k][1], f[i - 1][k - w[i]][1] + val[i][w[i]]);
}
}
i64 ans = 0;
for (int i = 0; i <= m; i++) {
ans = std::max({ans, f[n][i][0], f[n][i][1]});
}
std::cout << ans << '\n';
}
};
int main() {
Fast_IOS;
WORK work;
int T = 1;
// std::cin >> T;
while (T--) {
work.solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: -100
Wrong Answer
time: 59ms
memory: 144344kb
input:
3000 3000 10 70562 30723 79371 82224 63977 3362 26909 96449 48163 66159 4 18007 33590 80674 91139 4 10304 31694 70745 50656 10 63090 17226 13187 73881 38137 15237 55750 82751 75854 39658 8 95640 66120 87735 36388 44046 92415 6952 94772 9 60565 27904 98726 87052 35768 25453 14563 34273 92501 10 66332...
output:
171648352
result:
wrong answer 1st numbers differ - expected: '68279788', found: '171648352'