QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#466026#8005. Crossing the Borderucup-team052TL 3613ms274224kbC++234.0kb2024-07-07 14:53:542024-07-07 14:53:54

Judging History

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

  • [2024-07-07 14:53:54]
  • 评测
  • 测评结果:TL
  • 用时:3613ms
  • 内存:274224kb
  • [2024-07-07 14:53:54]
  • 提交

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

output:


result: