yukicoder No.974 - 最後の日までに

Source

ニコニコミュニティ
問題文

問題概要

省略

解法

省略

cLay（version 20200119-1）のコード

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

int N; ll A[52], B[52], C[52];

int s1; ll m1[1d6], g1[1d6];
int s2; ll m2[1d6], g2[1d6];

void dfs(int s, int e, ll m = 0, ll g = 0){
  if(s == e){
    arrInsert(s2,s2,g2,g,m2,m);
    return;
  }
  dfs(s+1, e, m+A[s], g);
  if(s+2 <= e) dfs(s+2, e, m-C[s+1], g+B[s+1]);
}

void ord(void){
  int i, k = 0;
  rsortA(s2, g2, m2);
  rep(i,s2){
    if(k && m2[i] <= m2[k-1]) continue;
    arrInsert(k,k,g2,g2[i],m2,m2[i]);
  }
  s2 = k;
}

ll solve(int n1, int n2){
  int i, k;
  ll res = 0;
  s1 = s2 = 0;

  dfs(0,n1); ord();
  s1 = s2;
  rep(i,s1) m1[i] = m2[i];
  rep(i,s1) g1[i] = g2[i];
  s2 = 0;
  dfs(n1,n1+n2); ord();

  k = s2-1;
  rep(i,s1){
    while(k-1>=0 && m1[i]+m2[k-1] >= 0) k--;
    if(m1[i]+m2[k] < 0) continue;
    res >?= g1[i] + g2[k];
  }

  return res;
}

{
  ll res = 0;
  rd(N,(A,B,C)(N));
  res >?= solve(N/2, N/+2);
  res >?= solve(N/2+1, (N/+2)-1);
  wt(res);
}

Current time: 2024年04月25日09時48分58秒
Last modified: 2020年01月19日05時34分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る

Logged in as: unknown user (not login)