省略
省略
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年05月04日23時38分49秒
Last modified: 2020年01月19日05時34分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete yukicoder
トップページに戻る
Logged in as: unknown user (not login)