QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358585#6194. Knapsack ProblemschrodingerstomTL 23ms5288kbC++143.5kb2024-03-19 21:14:252024-03-19 21:14:25

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 21:14:25]
  • 评测
  • 测评结果:TL
  • 用时:23ms
  • 内存:5288kb
  • [2024-03-19 21:14:25]
  • 提交

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...

result: