QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511042#5303. No Bug No Game114514abcWA 1ms3972kbC++141.4kb2024-08-09 15:35:052024-08-09 15:35:05

Judging History

你现在查看的是最新测评结果

  • [2024-08-09 15:35:05]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3972kb
  • [2024-08-09 15:35:05]
  • 提交

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'