QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#466026 | #8005. Crossing the Border | ucup-team052 | TL | 3613ms | 274224kb | C++23 | 4.0kb | 2024-07-07 14:53:54 | 2024-07-07 14:53:54 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
if(nega==-1) return -ans;
return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int add(int x,int y,int z) {return add(add(x,y),z);}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1LL*x*y%mod;}
inline int mul(int x,int y,int z) {return mul(mul(x,y),z);}
#define inc(x,y) x=add(x,y)
#define dec(x,y) x=sub(x,y)
#define N 20
struct Node
{
int w,c;
};
Node a[N+2];
bool cmp(Node x,Node y) {return x.c<y.c;}
int n,W,mn[1<<N],cnt[1<<N];
int sum[1<<N];
void bf()
{
sort(a,a+n,cmp);
for(int i=1;i<1<<n;i++)
{
int u=__builtin_ctz(i);
sum[i]=sum[i^(1<<u)]+a[u].w;
}
mn[0]=0,cnt[0]=1;
int ful=(1<<n)-1;
for(int i=1;i<1<<n;i++)
{
mn[i]=inf;
int u=31-__builtin_clz(i);
for(int st=i;st>=(1<<u);st=i&(st-1))
{
if(sum[st]<=W)
{
if(mn[i^st]+a[u].c<mn[i]) mn[i]=mn[i^st]+a[u].c,cnt[i]=0;
if(mn[i^st]+a[u].c==mn[i]) inc(cnt[i],cnt[i^st]);
}
}
}
printf("%d %d\n",mn[ful],cnt[ful]);
}
int l=20;
void fwt(int *f){
for(int i=1;i<(1<<l);i<<=1)for(int j=0;j<(1<<l);j+=i<<1)for(int k=0;k<i;++k){
f[i+j+k]=add(f[i+j+k],f[j+k]);
}
}
void ifwt(int *f){
for(int i=1;i<(1<<l);i<<=1)for(int j=0;j<(1<<l);j+=i<<1)for(int k=0;k<i;++k){
f[i+j+k]=sub(f[i+j+k],f[j+k]);
}
}
int F[21][1<<N],G[21][1<<N],H[21][1<<N];
void solve()
{
sort(a,a+n,cmp);
{
int ss=0;
for(int i=0;i<n;i++) ss+=a[i].w;
if(ss<=W)
{
printf("%d %d\n",a[n-1].c,1);
return ;
}
}
for(int i=1;i<1<<l;i++)
{
int u=__builtin_ctz(i);
sum[i]=sum[i^(1<<u)]+a[u].w;
}
mn[0]=0,cnt[0]=1;
int ful=(1<<l)-1;
for(int i=1;i<1<<l;i++)
{
mn[i]=inf;
int u=31-__builtin_clz(i);
for(int st=i;st>=(1<<u);st=i&(st-1))
{
if(sum[st]<=W)
{
if(mn[i^st]+a[u].c<mn[i]) mn[i]=mn[i^st]+a[u].c,cnt[i]=0;
if(mn[i^st]+a[u].c==mn[i]) cnt[i]=add(cnt[i],cnt[i^st]);
}
}
}
// for(int i=1;i<1<<n;i++) printf("%d %d %d\n",i,mn[i],cnt[i]);
// printf("%d %d\n",mn[ful],cnt[ful]);
int amn=inf; long long acnt=0;
if(n==21)
{
for(int i=0;i<1<<l;i++)
{
if(sum[i]+a[n-1].w<=W)
{
if(a[n-1].c+mn[i^ful]<amn) amn=a[n-1].c+mn[i^ful],acnt=0;
if(a[n-1].c+mn[i^ful]==amn) inc(acnt,cnt[i^ful]);
}
}
}
else
{
for(int i=0;i<1<<l;i++)
{
if(sum[i]+a[n-1].w+a[n-2].w<=W)
{
if(a[n-1].c+mn[i^ful]<amn) amn=a[n-1].c+mn[i^ful],acnt=0;
if(a[n-1].c+mn[i^ful]==amn) inc(acnt,cnt[i^ful]);
}
}
for(int i=0;i<(1<<l);++i){
if(a[n-1].w+sum[i]<=W)F[__builtin_popcount(i)][i]=1;
if(a[n-2].w+sum[i]<=W)G[__builtin_popcount(i)][i]=1;
}
for(int i=0;i<=l;++i){
fwt(F[i]);
fwt(G[i]);
}
for(int j=0;j<=l;++j){
for(int k=0;k+j<=l;++k){
for(int i=0;i<(1<<l);++i){
H[j+k][i]=add(H[j+k][i],mul(F[j][i],G[k][i]));
}
}
}
for(int i=0;i<=l;++i){
ifwt(H[i]);
}
for(int i=0;i<(1<<l);++i){
int cur=H[__builtin_popcount(i)][i];
if(cur){
// printf("%d : %d\n",i,cur);
if(a[n-1].c+a[n-2].c+mn[ful^i]<amn){
amn=a[n-1].c+a[n-2].c+mn[ful^i];
acnt=0;
}
if(a[n-1].c+a[n-2].c+mn[ful^i]==amn){
inc(acnt,mul(cur,cnt[ful^i]));
}
}
}
}
printf("%d %lld\n",amn,acnt%mod);
}
signed main()
{
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
cin>>n>>W;
for(int i=0;i<n;i++) a[i].w=read(),a[i].c=read();
if(n<=20) bf();
else solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7932kb
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: 224ms
memory: 14600kb
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: 2365ms
memory: 16020kb
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: 2133ms
memory: 16088kb
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: 2983ms
memory: 274096kb
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: 3168ms
memory: 274148kb
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: 2044ms
memory: 274128kb
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: 0
Accepted
time: 3339ms
memory: 274164kb
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:
28157573 762
result:
ok 2 number(s): "28157573 762"
Test #9:
score: 0
Accepted
time: 3311ms
memory: 274116kb
input:
22 48889995 670320 2222256 1480754 2407444 2099421 2592632 3936255 2777820 959515 2963008 4781765 3333384 5446683 3518572 1207621 3703760 5965481 3888948 5353960 4074136 3991352 4259324 3814761 4629700 7642867 4814888 6776227 5000076 7737927 5185264 6271909 5370452 8235670 5555640 5720862 5740828 94...
output:
15926168 295
result:
ok 2 number(s): "15926168 295"
Test #10:
score: 0
Accepted
time: 3406ms
memory: 274092kb
input:
22 48889995 3609129 2222256 4285697 2407444 1507969 2592632 1231013 2777820 3176763 2963008 3473072 3148196 7482780 3518572 2891596 3703760 8705206 3888948 7267923 4074136 7325365 4259324 2847372 4444512 5957854 4629700 6070319 4814888 5000188 5000076 6651643 5185264 4854109 5370452 5385621 5555640 ...
output:
15000228 109
result:
ok 2 number(s): "15000228 109"
Test #11:
score: 0
Accepted
time: 3423ms
memory: 274136kb
input:
22 48889995 1216303 2222260 1359130 2415500 3584343 2608740 5573601 2801980 6497030 2995220 961106 3188460 7210397 3381700 7437984 3574940 3653310 3768180 8153230 3961420 9078129 4154660 9339995 4347900 9546227 4541140 5979651 4927620 8415111 5120860 2355876 5314100 5268961 5507340 5513979 5700580 5...
output:
14976100 7
result:
ok 2 number(s): "14976100 7"
Test #12:
score: 0
Accepted
time: 3302ms
memory: 274144kb
input:
22 48579995 995517 4416345 4162361 4608360 689494 4800375 1751672 4992390 3152622 5184405 6822783 5376420 9853978 5568435 8144298 5760450 403922 5952465 4762546 6144480 96738 6336495 3332168 6528510 3046767 6720525 612840 6912540 12718394 7104555 12544817 7296570 932656 7488585 13902077 7680600 1518...
output:
21505680 2766
result:
ok 2 number(s): "21505680 2766"
Test #13:
score: 0
Accepted
time: 3465ms
memory: 274096kb
input:
22 48579995 1487345 4416345 2506907 4608360 4972266 4800375 5406373 4992390 7889100 5184405 9894143 5376420 3260719 5568435 3583436 5760450 2820541 5952465 8370133 6144480 491071 6336495 2885341 6528510 2489830 6720525 2929470 6912540 6880314 7296570 4020302 7488585 1341652 7680600 13092883 7872615 ...
output:
21889710 2841
result:
ok 2 number(s): "21889710 2841"
Test #14:
score: 0
Accepted
time: 3613ms
memory: 274192kb
input:
22 48579995 2167618 4416345 8701572 4608360 8901658 4800375 2606668 4992390 10331331 5184405 473563 5376420 9425532 5568435 2521056 5760450 7409167 5952465 5163980 6144480 11569213 6336495 2178000 6528510 3109142 6720525 9789269 6912540 4418312 7104555 4345642 7296570 8296204 7680600 7135437 7872615...
output:
21121650 8
result:
ok 2 number(s): "21121650 8"
Test #15:
score: 0
Accepted
time: 3347ms
memory: 274072kb
input:
22 48579995 185663 4416345 6058344 4608360 331879 4800375 1065291 4992390 8966703 5184405 8105358 5376420 5217326 5568435 8799150 5760450 9027629 5952465 8032986 6144480 4436166 6336495 12199531 6528510 8750754 6720525 82844 7104555 1853547 7296570 5898163 7488585 1934865 7680600 1839565 7872615 633...
output:
20545605 26
result:
ok 2 number(s): "20545605 26"
Test #16:
score: 0
Accepted
time: 3201ms
memory: 274148kb
input:
22 48579995 15151 4416345 734549 4608360 7319925 4800375 2129913 4992390 853818 5376420 10141848 5568435 767573 5760450 3980988 5952465 3315870 6144480 2531255 6336495 5624435 6528510 6571293 6720525 40928 6912540 10363672 7104555 1284631 7296570 14701697 7488585 14642456 7680600 322573 7872615 1043...
output:
21697695 4991
result:
ok 2 number(s): "21697695 4991"
Test #17:
score: 0
Accepted
time: 3397ms
memory: 274220kb
input:
22 49898989 7739655 4536267 3933324 4733496 8591811 4930725 9087440 5325183 7835571 5522412 4318275 5719641 4661526 5916870 4200111 6114099 5057614 6311328 921304 6508557 4668507 6705786 5557323 6903015 4273093 7100244 6563270 7297473 9919216 7494702 3400922 7691931 11079804 7889160 100670 8086389 1...
output:
20906274 1
result:
ok 2 number(s): "20906274 1"
Test #18:
score: 0
Accepted
time: 3264ms
memory: 274144kb
input:
22 49898989 6061313 4536267 716781 4733496 305819 4930725 6315187 5127954 4257670 5325183 2230859 5522412 1085663 5719641 5327241 5916870 1902077 6114099 4171313 6311328 10963222 6508557 1747036 6903015 10948695 7100244 3677364 7297473 11817601 7494702 11781634 7691931 3295539 7889160 1325434 808638...
output:
20511816 50
result:
ok 2 number(s): "20511816 50"
Test #19:
score: 0
Accepted
time: 3407ms
memory: 274164kb
input:
22 49898979 1647035 4536250 175922 4717700 8292866 4899150 2096187 5080600 10066004 5262050 961380 5443500 1647976 5624950 5110920 5987850 2028528 6169300 8462757 6713650 1216165 6895100 1260925 7076550 8167307 7258000 7304251 7439450 11040257 7620900 5536709 7802350 4725071 7983800 3148347 8165250 ...
output:
21592550 54
result:
ok 2 number(s): "21592550 54"
Test #20:
score: 0
Accepted
time: 3296ms
memory: 274076kb
input:
22 49898919 4880960 3402175 5824531 3674349 2692142 3810436 219059 3946523 3955872 4082610 1597316 4354784 6797847 4490871 1286029 4626958 3989070 4763045 6096677 4899132 6378309 5035219 3025127 5171306 7099640 5307393 9936888 5443480 7942273 5579567 5288035 5715654 6910366 5851741 588733 5987828 88...
output:
15377831 2
result:
ok 2 number(s): "15377831 2"
Test #21:
score: 0
Accepted
time: 3317ms
memory: 274156kb
input:
22 49898919 5878918 3066492 6028670 3184434 1748377 3302376 3583403 3420318 61448 3538260 4692284 3656202 5129355 3774144 6440565 4010028 1002813 4127970 1728560 4245912 4721603 4363854 6446718 4481796 4118552 4599738 4479205 4717680 8610916 4835622 63195 4953564 9769813 5071506 5123156 5189448 4790...
output:
13445388 2
result:
ok 2 number(s): "13445388 2"
Test #22:
score: 0
Accepted
time: 3309ms
memory: 274132kb
input:
22 49898919 4757745 2721750 1190291 2830620 122673 2939490 5285455 3048360 5154097 3157230 3426786 3266100 2776798 3374970 6808419 3483840 7113299 3592710 4948131 3701580 4444440 3810450 1054709 3919320 4310982 4028190 8200366 4137060 1136653 4245930 4064806 4354800 3259693 4463670 5015241 4572540 8...
output:
12084570 61
result:
ok 2 number(s): "12084570 61"
Test #23:
score: 0
Accepted
time: 3327ms
memory: 274224kb
input:
22 49898919 4700657 2598900 3031551 2702856 2474511 2806812 5253209 2910768 4420840 3014724 5145346 3118680 2600255 3222636 1962472 3326592 6224012 3430548 2681629 3534504 2745527 3638460 5992867 3742416 2067411 3846372 6330981 3950328 5060577 4054284 6543128 4262196 5788423 4366152 5569899 4470108 ...
output:
11435160 17
result:
ok 2 number(s): "11435160 17"
Test #24:
score: 0
Accepted
time: 3375ms
memory: 274064kb
input:
22 49898919 3161907 2948554 1025254 3076752 5761371 3204950 508930 3333148 4685707 3461346 5326061 3589544 5702566 3717742 6533903 3845940 4153649 4102336 1132247 4230534 8560233 4358732 8679182 4486930 4205825 4615128 739891 4743326 7020873 4871524 6479109 4999722 5459256 5127920 6220335 5256118 33...
output:
13332592 3
result:
ok 2 number(s): "13332592 3"
Test #25:
score: 0
Accepted
time: 3301ms
memory: 274136kb
input:
22 49998920 5432634 2499936 863708 2604100 2752108 2708264 5483524 2812428 3143863 2916592 3862668 3020756 3252628 3124920 5204497 3229084 1249648 3333248 3953145 3541576 1507722 3645740 8393362 3749904 6439438 3854068 4362518 3958232 4233238 4062396 5523854 4166560 9201858 4270724 2455377 4374888 8...
output:
11145548 2
result:
ok 2 number(s): "11145548 2"
Test #26:
score: 0
Accepted
time: 3389ms
memory: 274164kb
input:
22 49998920 6166390 2727208 5195387 2851172 2483572 2975136 6640764 3099100 2033798 3223064 5969501 3347028 7968425 3470992 857128 3594956 6854182 3718920 2064030 3842884 8893787 3966848 8849735 4090812 743604 4214776 2540982 4338740 7410235 4462704 2247651 4586668 785337 4710632 8843312 4834596 508...
output:
12024508 5
result:
ok 2 number(s): "12024508 5"
Test #27:
score: 0
Accepted
time: 3260ms
memory: 274164kb
input:
22 49998920 1851866 2499926 1743639 2613559 58569 2727192 6420362 2840825 3807544 2954458 2258556 3068091 7054799 3181724 3607029 3295357 5664438 3408990 7048880 3522623 6084252 3636256 4253765 3749889 3691283 3863522 4746341 3977155 4213709 4090788 5646732 4204421 8240035 4318054 9886432 4431687 48...
output:
11249667 4
result:
ok 2 number(s): "11249667 4"
Test #28:
score: -100
Time Limit Exceeded
input:
22 15 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1