QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#219424 | #5303. No Bug No Game | isaunoya | WA | 0ms | 74412kb | C++23 | 2.4kb | 2023-10-19 14:34:09 | 2023-10-19 14:34:10 |
Judging History
answer
#include <bits/stdc++.h>
#ifndef LOCAL
#define debug(...) 42
#else
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#endif
#define rep1(a) for (int i = 0; i < a; i++)
#define rep2(i, a) for (int i = 0; i < a; i++)
#define rep3(i, a, b) for (int i = a; i < b; i++)
#define rep4(i, a, b, c) for (int i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
x = x > y ? x : y;
}
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
template <class T> using vc = vector<T>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
mt19937 rng(time(NULL));
const int inf = 1000000000;
const ll lnf = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
int n, k;
const int N = 3010;
int dp[N][N];
int pre[N][N];
int suf[N][N];
int p[N];
int a[N][11];
void solve() {
memset(pre, 0xcf, sizeof pre);
memset(suf, 0xcf, sizeof suf);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> p[i];
for (int j = 1; j <= p[i]; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
memcpy(pre[i], pre[i - 1], sizeof pre[i]);
for (int j = p[i]; j <= k; j++) {
cmax(pre[i][j], pre[i - 1][j - p[i]] + a[i][p[i]]);
}
}
for (int i = n; i >= 1; i--) {
memcpy(suf[i], suf[i + 1], sizeof suf[i]);
for (int j = p[i]; j <= k; j++) {
cmax(suf[i][j], suf[i + 1][j - p[i]] + a[i][p[i]]);
}
}
auto get = [&](int p, int rem) {
int res = 0;
for (int i = 0; i <= rem; i++) {
cmax(res, pre[p - 1][i] + suf[p + 1][rem - i]);
}
return res;
};
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= p[i]; j++) {
int rem = k - j;
cmax(ans, a[i][j] + get(i, rem));
}
}
cmax(ans, pre[n][k]);
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 74412kb
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3
output:
3
result:
wrong answer 1st numbers differ - expected: '9', found: '3'