QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#390971#8005. Crossing the BordermarherTL 4379ms122276kbC++142.8kb2024-04-16 10:00:342024-04-16 10:00:34

Judging History

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

  • [2024-04-16 10:00:34]
  • 评测
  • 测评结果:TL
  • 用时:4379ms
  • 内存:122276kb
  • [2024-04-16 10:00:34]
  • 提交

answer

#pragma GCC optimize("Ofast","inline")
#include<bits/stdc++.h>
#define lb(x) (x&(-x))
using namespace std;
const int N=(1<<22),M=22,mod=998244353;

int md(int x)
{
    return x>=mod?x-mod:x;
}

struct node
{
    int w,s;

    friend node operator+(node a,node b)
    {
        if(a.w==b.w)return (node){a.w,md(a.s+b.s)};
        return a.w<b.w?a:b;
    }
    
    friend node operator*(node a,node b)
    {
        return (node){a.w+b.w,(int)(1ll*a.s*b.s%mod)};
    }
}f[N],g[N];

struct poi
{
    int c,w;

    friend bool operator<(poi a,poi b)
    {
        return a.c<b.c;
    }
}a[M];

int n,m,sum[N],w,mx[N],mb[N],A[N],top,cc[N];
// vector<int>B[1<<11];
int *B[1<<11];

int cmp1(int a,int b)
{
    return sum[a]>sum[b];
}

int cmp2(int a,int b)
{
    return sum[a]<sum[b];
}

void solve(int m,int d)
{
    for(int i=1;i<(1<<m);i++)
    {
        int t=i<<d;
        if(sum[t]<=w)
        {
            f[t]=(node){mx[t],1};
            continue;
        }
        f[t].w=2e9;
        int p=t^lb(t);
        for(int s=p;s;s=(s-1)&p)f[t]=f[t]+(f[s]*f[t^s]);
    }
}

int main()
{
    // freopen("in","r",stdin);
    // freopen("out","w",stdout);
    cin>>n>>w;m=n/2;
    for(int i=0;i<n;i++)cin>>a[i].w>>a[i].c;
    sort(a,a+n);
    for(int i=0;i<n;i++)sum[1<<i]=a[i].w,mx[1<<i]=a[i].c,mb[1<<i]=(1<<i);
    for(int i=1;i<(1<<n);i++)if(lb(i)^i)sum[i]=sum[i^lb(i)]+sum[lb(i)],mx[i]=max(mx[i^lb(i)],mx[lb(i)]),mb[i]=mb[i-1];
    for(int i=0;i<(1<<n-m);i++)
    {
        for(int s=(i^mb[i]);s;s=(s-1)&(i^mb[i]))if(sum[(i^s)<<m]<=w)++cc[i];
        B[i]=new int[cc[i]+1];cc[i]=0;
        for(int s=(i^mb[i]);s;s=(s-1)&(i^mb[i]))if(sum[(i^s)<<m]<=w)B[i][cc[i]++]=(s<<m);
        B[i][cc[i]++];sort(B[i],B[i]+cc[i],cmp2);
    }
    f[0]=(node){0,1};solve(m,0);solve(n-m,m);
    for(int i=1;i<(1<<m);i++)
    {
        top=0;
        for(int s=(i&(i-1));s;s=((s-1)&i))A[top++]=s;A[top++]=0;
        sort(A,A+top,cmp1);
        for(int s=0;s<(1<<n-m);s++)
        {
            node now;now.w=2e9;
            for(int j=0;j<top;j++)g[(s<<m)|A[j]]=now=now+f[(s<<m)|A[j]];
        }
        for(int s=1;s<(1<<n-m);s++)
        {
            int pos=0,t=(s<<m)|i,rw=mx[s<<m];f[t].w=2e9;
            if(sum[t]<=w)
            {
                f[t]=(node){mx[t],1};
                continue;
            }
            for(int j=0;j<cc[s];j++)
            {
                int x=B[s][j];
                if(sum[(s<<m)^x]<=w)f[t]=f[t]+(f[i|x]*(node){rw,1});
                while(pos<top&&sum[i|(s<<m)]-sum[A[pos]]-sum[x]<=w)pos++;
                if(pos)f[t]=f[t]+(g[A[pos-1]|x]*(node){rw,1});
            }
        }
    }
    cout<<f[(1<<n)-1].w<<' '<<f[(1<<n)-1].s<<'\n';
    cerr<<1.0*clock()/CLOCKS_PER_SEC;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 16184kb

input:

5 5
3 5
1 4
2 3
2 2
2 1

output:

9 4

result:

ok 2 number(s): "9 4"

Test #2:

score: 0
Accepted
time: 91ms
memory: 26528kb

input:

18 10000000
956231 904623
1692946 1796774
1081323 1170319
3218792 2542661
3183376 3037270
1869132 1442561
35436 35018
1564635 1939950
1847344 2006043
755870 899310
1671882 2057413
1369264 1338951
3132483 3504034
2056224 1825640
1840949 1562071
1514040 1405352
2300821 2421801
2466540 3004920

output:

9391997 70

result:

ok 2 number(s): "9391997 70"

Test #3:

score: 0
Accepted
time: 572ms
memory: 45032kb

input:

20 10000000
1289384 1416015
1692778 1966748
1747794 1708650
2885387 2925290
2516650 2410838
2202363 2092667
368691 407497
1897764 1902790
180541 224758
1089173 1075924
2005212 1743637
702568 566295
465783 369143
2722863 2902398
174068 150211
513930 519657
1634023 1313239
1133070 1040937
961394 11066...

output:

6331196 89

result:

ok 2 number(s): "6331196 89"

Test #4:

score: 0
Accepted
time: 1297ms
memory: 73820kb

input:

21 10000000
1432782 1230128
1693282 1456826
605524 521515
2742745 3427204
2231114 2129928
2345527 2397808
511783 521160
2041234 2313965
2323807 2603481
1232121 1410811
719508 850004
416942 495559
2180169 2579591
1580089 1786914
2317568 2292171
1514260 1143717
1348703 1495001
562052 525544
2818854 23...

output:

9336572 5

result:

ok 2 number(s): "9336572 5"

Test #5:

score: 0
Accepted
time: 4379ms
memory: 121976kb

input:

22 10000000
1562592 1176882
1693226 1513484
2293770 2757728
2612851 3010518
1971354 2392268
2475363 2035487
641627 684375
2171036 2181775
1544541 1633457
1361981 1060447
2277948 2792254
157192 141039
1011327 1139897
541119 577682
1538276 1451191
2423314 2061841
1088919 1154927
42526 43789
1779858 16...

output:

8019829 516

result:

ok 2 number(s): "8019829 516"

Test #6:

score: 0
Accepted
time: 4250ms
memory: 121436kb

input:

22 50000000
9900000 50000000
9800000 50000000
9700000 50000000
9600000 50000000
9500000 50000000
9400000 50000000
9300000 50000000
9200000 50000000
9100000 50000000
9190000 50000000
9180000 50000000
9170000 50000000
9160000 50000000
9150000 50000000
9140000 50000000
9130000 50000000
9120000 50000000...

output:

250000000 659827482

result:

ok 2 number(s): "250000000 659827482"

Test #7:

score: 0
Accepted
time: 2050ms
memory: 122276kb

input:

22 49989999
9515787 13633636
7804670 14201704
4490825 15337840
10846676 15905908
4649834 16473976
13564408 17042044
26330177 17610112
31079612 18178180
9508811 18746248
11012937 19314316
9221231 19882384
35630511 20450452
33570222 21018520
33987302 22154656
28961982 22722724
29610359 23290792
342743...

output:

297099616 239005143

result:

ok 2 number(s): "297099616 239005143"

Test #8:

score: -100
Time Limit Exceeded

input:

22 49889999
4418358 4535448
7690530 4724425
3667793 4913402
8304776 5102379
2539846 5291356
2404119 5480333
2368750 5669310
3896314 5858287
6349833 6047264
10839169 6425218
10867512 6614195
9018761 6803172
5396983 6992149
2026994 7181126
6093366 7370103
10403853 7559080
5578332 7748057
13492459 7937...

output:


result: