QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511042 | #5303. No Bug No Game | 114514abc | WA | 1ms | 3972kb | C++14 | 1.4kb | 2024-08-09 15:35:05 | 2024-08-09 15:35:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 3005;
struct Node{
int l, r;
vector<int>e;
}t[N * 4];
int dp[N], n, k, w[N][30], p[N], ans;
void build(int p, int l, int r){
t[p].l = l, t[p].r = r, t[p].e.clear();
if(l == r){
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
}
void updata(int p, int l, int r, int x){
if(r < l)return;
if(l <= t[p].l && t[p].r >= r){
t[p].e.push_back(x);
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if(l <= mid)updata(p * 2, l, r, x);
if(r > mid)updata(p * 2 + 1, l, r, x);
}
void dfs(int pp){
int f[N];
for(int i = 0; i <= k; i++){
f[i] = dp[i];
}
for(auto v : t[pp].e){
for(int i = k; i >= p[v]; i--){
dp[i] = max(dp[i], dp[i - p[v]] + w[v][p[v]]);
}
}
if(t[pp].l == t[pp].r){
for(int i = 0; i <= p[t[pp].l] && k - i >= 0; ++i){
ans = max(ans, dp[k - i] + w[t[pp].l][i]);
}
}
else{
dfs(pp * 2);
dfs(pp * 2 + 1);
}
for(int i = 1; i <= k; ++i){
dp[i] = f[i];
}
}
int main(){
cin >> n >> k;
build(1, 1, n);
for(int i = 1; i <= n; ++i){
cin >> p[i];
for(int j = 1; j <= p[i]; j++){
cin >> w[i][j];
}
updata(1, 1, i - 1, i);
updata(1, i + 1, 1, i);
}
dfs(1);
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3972kb
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3
output:
7
result:
wrong answer 1st numbers differ - expected: '9', found: '7'