QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#390971 | #8005. Crossing the Border | marher | TL | 4379ms | 122276kb | C++14 | 2.8kb | 2024-04-16 10:00:34 | 2024-04-16 10:00:34 |
Judging History
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...