QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#377266 | #6194. Knapsack Problem | Crying | TL | 45ms | 4680kb | C++14 | 1.5kb | 2024-04-05 10:11:35 | 2024-04-05 10:11:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std; typedef long long ll;
const ll INF = 1e18,M = 30;
void tomax(ll& x,ll y){x = (x>y)?(x):(y);}
int T,k,c[16],a[4];
ll dp[M+1][4096],g[16][625],pw[5];
void solve(){
pw[0] = 1,pw[1] = 5,pw[2] = 25,pw[3] = 125,pw[4] = 625;
cin>>k;
for(int i=1;i<(1<<k);i++)cin>>c[i]; for(int i=0;i<k;i++)cin>>a[i];
for(int i=0;i<(1<<k);i++)for(int S=0;S<pw[k];S++)g[i][S] = -INF;
for(int S=0;S<(1<<(1<<k));S++)if(!(S&1)){
int lim = 0,nxt = 0;
for(int j=0;j<k;j++){
int cnt = 0;
for(int p=1;p<(1<<k);p++)if( (S>>p&1) && (p>>j&1) ){
lim ^= 1<<j;
cnt++;
}
nxt += (cnt>>1) * pw[j];
}
ll sum = 0;
for(int p=1;p<(1<<k);p++)if(S>>p&1)sum += c[p];
tomax(g[lim][nxt],sum);
}
for(int i=0;i<=M;i++)for(int S=0;S<(1<<3*k);S++)dp[i][S] = -INF;
dp[0][0] = 0;
for(int i=0;i<M;i++){
ll pv,qv;
for(int S=0;S<(1<<3*k);S++)if((pv=dp[i][S]) != -INF){
int lim = 0;
for(int j=0,p=7;j<k;j++,p<<=3){
int val = ((S&p)>>3*j)&1;
lim |= (val != (a[j]>>i&1)) << j;
}
for(int T=0;T<pw[k];T++)if((qv=g[lim][T]) != -INF){
int nxt = 0;
for(int j=0,p=7;j<k;j++,p<<=3){
int val = (((S&p)>>3*j)+(lim>>j&1))/2 + (T/pw[j]%5);
assert(val <= 7);
nxt |= val << (3*j);
}
tomax(dp[i+1][nxt],pv + (qv << i));
}
}
}
ll ans = dp[M][0];
(ans == -INF) ? (cout<<"-1\n") : (cout<<ans<<"\n");
}
int main(){
cin>>T;
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 45ms
memory: 4680kb
input:
3 2 1 2 4 4 5 3 3226252 19270256 2430652 1187613 12496062 10286165 17494834 24 85 34 4 901133 6693218 13245489 14740234 16186210 11382783 19277321 3855635 16523184 10168517 16195031 971041 10303441 8395899 11618555 529321239 218214127 92942310 207467810
output:
18 1949753378 7832404777567179
result:
ok 3 number(s): "18 1949753378 7832404777567179"
Test #2:
score: -100
Time Limit Exceeded
input:
100 4 4488409 9842893 14331290 11289097 15777479 21131954 25620334 6146092 10634508 15988956 20477387 17435190 21923584 27278027 31766493 200477197 258791439 590664017 982949628 4 5484152 19851747 25335961 6555937 12039831 26407861 31891996 10897184 16381166 30749333 36233145 17453055 22937114 37304...
output:
16156444320083421 24565535429631234 29418802996321901 30685727712782520 21026118053726857 27272339796311010 28831028447377015 34577176834491128 9058894962996375 21525085254465501 6657186892229297 16750628911275484 11217846865301187 12674726744043780 33873234230125448 3890237279573366 319038768614465...