Codeforces Round #681 (based on VK Cup 2019-2020 - Final) DIV1 D問題/Final C問題 - Sum

Source

Codeforces Round #681 (based on VK Cup 2019-2020 - Final) DIV1 D問題 (1750pt)
VK Cup 2019-2020 - Final Round C問題 (1750pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20201102-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int N, K;
vector<ll> A[3000];
int sz[3000];
ll sm[3000], dp[20][3001], res;

void solve(int d, int s, int t){
  if(t-s == 1){
    ll tmp = 0;
    res >?= dp[d][K];
    rep(i,A[s].size()){
      tmp += A[s][i];
      res >?= tmp + dp[d][K-1-i];
    }
    return;
  }

  int m = (s + t) / 2;

  rep(j,K+1) dp[d+1][j] = dp[d][j];
  rep(i,s,m) rrep(j,sz[i],K+1) dp[d+1][j] >?= dp[d+1][j-sz[i]] + sm[i];
  solve(d+1, m, t);

  rep(j,K+1) dp[d+1][j] = dp[d][j];
  rep(i,m,t) rrep(j,sz[i],K+1) dp[d+1][j] >?= dp[d+1][j-sz[i]] + sm[i];
  solve(d+1, s, m);
}

{
  rd(N,K);
  rep(i,N) REP(rd_int()) A[i].push_back(rd_ll());
  rep(i,N) while(A[i].size() > K) A[i].pop_back();
  rep(i,N) sz[i] = A[i].size();
  rep(i,N) sm[i] = sum(A[i](sz[i]));
  solve(0, 0, N);
  wt(res);
}

Current time: 2024年04月25日12時37分23秒
Last modified: 2020年11月03日08時07分59秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF681 CF_DIV1_D
トップページに戻る

Logged in as: unknown user (not login)