QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#358585 | #6194. Knapsack Problem | schrodingerstom | TL | 23ms | 5288kb | C++14 | 3.5kb | 2024-03-19 21:14:25 | 2024-03-19 21:14:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
bool memBeg;
template<typename T> void chkmin(T &x,T y) {if(x>y) x=y;}
template<typename T> void chkmax(T &x,T y) {if(x<y) x=y;}
constexpr int mod=1e9+7;
void inc(int &x,int y) {x+=y; x-=(x>=mod)*mod;}
void dec(int &x,int y) {x-=y; x+=(x<0)*mod;}
constexpr int add(int x,int y) {return (x+y>=mod)?x+y-mod:x+y;}
constexpr int sub(int x,int y) {return (x<y)?x-y+mod:x-y;}
constexpr int quick_pow(int x,int times) {
int ret=1;
for(;times;times>>=1,x=1ll*x*x%mod) {
if(times&1) ret=1ll*ret*x%mod;
}
return ret;
}
constexpr int D=30;
constexpr int lim=9;
constexpr int maxn=25;
constexpr int maxK=10;
constexpr int maxmask1=5005;
constexpr int maxmask2=6.6e4+5;
constexpr ll INF=0x3f3f3f3f3f3f3f3f;
int K,pK,c[maxn],a[maxK];
// int trans1[maxn][maxmask2];
int vld[maxmask2],top,go[maxmask1],go2[maxmask2];
ll maxx[maxmask2],nmaxx[maxmask2];
bool good[maxmask2];
void mian() {
scanf("%d",&K);
for(int i=1;i<(1<<K);i++) scanf("%d",&c[i]);
for(int i=0;i<K;i++) scanf("%d",&a[i]);
int full1=1,full2=1;
for(int i=0;i<K;i++) {
full1<<=(K-1); full2<<=K;
}
fill(maxx,maxx+full1,-INF);
fill(good,good+full2,false);
fill(go,go+full1,-1);
fill(go2,go2+full2,-1);
maxx[0]=0ll;
top=0;
for(int i=0;i<full2;i++) {
vld[top++]=i; good[i]=true;
for(int j=0;j<K;j++) {
if(((i>>(j*K))&((1<<K)-1))>lim) {
top--; good[i]=false; break;
}
}
}
for(int i=0;i<full1;i++) {
int ni=0,pi=i,pni=0;
for(int k=0;k<K;k++) {
ni=((pi&((1<<(K-1))-1))<<1)<<(k*K)|ni;
pni=(pi&((1<<(K-1))-1))<<(k*K)|pni;
if((pi&((1<<(K-1))-1))>=(lim+1)/2) {
ni=-1; break;
}
pi>>=(K-1);
}
if(ni!=-1) {
go[i]=ni; go2[pni]=i;
}
}
for(int i=D-1;i>=0;i--) {
fill(maxx+full1,maxx+full2,-INF);
for(int j=full1-1;j>=0;j--) {
ll now=maxx[j]; maxx[j]=-INF;
if(now<0) continue;
int nj=go[j];
for(int k=0;k<K;k++) nj|=((a[k]>>i)&1)<<(k*K);
if(good[nj]!=-1) maxx[nj]=now;
}
for(int j=1;j<(1<<K);j++) {
fill(nmaxx,nmaxx+full2,-INF);
for(int kk=0;kk<top;kk++) {
int k=vld[kk];
if(maxx[k]<0) continue;
chkmax(nmaxx[k],maxx[k]);
// int nk=trans1[j][k];
int nk=k;
for(int t=0;t<K;t++) {
if(j&(1<<t)) {
if((nk>>(t*K))&((1<<K)-1)) nk-=1<<(t*K);
else {nk=-1; break;}
}
}
if(nk!=-1) chkmax(nmaxx[nk],maxx[k]+(((ll)c[j])<<i));
}
memcpy(maxx,nmaxx,sizeof(ll)*full2);
}
fill(nmaxx,nmaxx+full1,-INF);
for(int jj=0;jj<top;jj++) {
int j=vld[jj],nj=0;
if(go2[j]==-1) continue;
chkmax(nmaxx[go2[j]],maxx[j]);
}
memcpy(maxx,nmaxx,sizeof(ll)*full1);
}
printf("%lld\n",max(-1ll,maxx[0]));
}
bool memEn;
void fl() {
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
int main() {
fprintf(stderr,"%.24lf\n",fabs(&memEn-&memBeg)/1024.0/1024.0);
// fl();
int _; scanf("%d",&_);
while(_--) mian();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 23ms
memory: 5288kb
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...