QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149616#5480. New Year FestivallgvcTL 5387ms95968kbC++233.4kb2023-08-24 22:56:402023-08-24 22:56:40

Judging History

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

  • [2023-08-24 22:56:40]
  • 评测
  • 测评结果:TL
  • 用时:5387ms
  • 内存:95968kb
  • [2023-08-24 22:56:40]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define pai 3.141592653589793238462643383279502884197169399375105820
#define eps 0.00000001
#define ULL unsigned long long
#define LL long long
#define INF 0x3f3f3f3f
#define INF_LL 0x3f3f3f3f3f3f3f3f
static char buf[1000000],*paa=buf,*pd=buf;
static char buf2[1000000],*pp=buf2;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline void pc(char ch){
	if(pp-buf2==1000000) fwrite(buf2,1,1000000,stdout),pp=buf2;
	*pp++=ch;
}
inline void pcc(){
	fwrite(buf2,1,pp-buf2,stdout);
	pp=buf2;
}
inline int read(void){
	int w=1;
	register int x(0);register char c(getchar());
	while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return w*x;
}
void write(int x){
	static int sta[20];
	int top=0;
	do{
		sta[top++]=x%10,x/=10;
	}while(x);
	while(top) pc(sta[--top]+48);
}
void we(int x){
	write(x);
	pc('\n');
}
struct n_t{
	int x,y;
};
inline bool cmp(n_t m,n_t n) {
	return m.x<n.x;
}
int N,s[15],l[15],f[15],p[15],q[15],x[15][70],y[15][70],vi[2000009],as=INF_LL;
std::vector<n_t> dp,dq,stt[2000009];
inline int qr(int x) {
	if(x>dq[dq.size()-1].x) return dq[dq.size()-1].y;
	if(dq.size()==1) return dq[0].y;
	int l=0,r=dq.size()-2,md;
	while(l<r) {
		md=(l+r+1)>>1;
		if(x>=dq[md].x) l=md;else r=md-1;
	}
	return dq[l].y+(dq[l+1].y-dq[l].y)/(dq[l+1].x-dq[l].x)*(x-dq[l].x);
}
std::vector<n_t> ff(int xx) {
	dp.clear();
	dq.clear();
	dp.push_back((n_t){0,0});
	dp.push_back((n_t){100000000,0});
	int vq=0;
	for(int i=1;i<=xx;i++) {
		vq=vq*N+f[i];
		if(i<=6&&vi[vq]) {
			dp=stt[vq];
			if(dp.empty()) return dp;
			continue;
		}
		dq=dp;
		for(int j=1;j<=s[f[i]];j++) {
			if(x[f[i]][j]>=dq[0].x) dp.push_back((n_t){x[f[i]][j],qr(x[f[i]][j])});
		}
		dq.clear();
		std::sort(dp.begin(),dp.end(),cmp);
		for(int j=0;j<dp.size();j++) if(dp[j].x<=x[f[i]][s[f[i]]]&&dp[j].x>=x[f[i]][1]) dq.push_back(dp[j]);
		int st=1;
		for(int j=0;j<dq.size();j++) {
			while(st+1<s[f[i]]&&dq[j].x>=x[f[i]][st+1]) st++;
			if(s[f[i]]==1) dq[j].y+=y[f[i]][1];
			else dq[j].y+=y[f[i]][st]+(y[f[i]][st+1]-y[f[i]][st])/(x[f[i]][st+1]-x[f[i]][st])*(dq[j].x-x[f[i]][st]);
			dq[j].x+=l[f[i]];
		}
		if(dq.empty()) {
			if(i<=6) vi[vq]=1;
			return dq;
		}
		dp.clear();
		dp.push_back(dq[0]);
		for(int j=1;j<dq.size();j++) {
			if(dq[j].x!=dq[j-1].x) dp.push_back(dq[j]);
		}
		for(int j=1;j<dp.size();j++) {
			dp[j].y=std::min(dp[j].y,dp[j-1].y);
		}
		if(i<=6) {
			vi[vq]=1;
			stt[vq]=dp;
		}
	}	
	return dp;
}
inline void tryy(int x) {
	int k=0,ct=1;
	for(int i=1;i<=N;i++) if((x>>i-1)&1) p[++k]=i,q[k]=k-1;
	for(int i=1;i<=k;i++) ct=ct*i;
	while(ct--) {
		for(int i=1;i<=k;i++) f[i]=p[q[i]+1];
		dq=ff(k);
		if(!dq.empty()) as=std::min(as,dq[dq.size()-1].y);
		std::next_permutation(q+1,q+k+1);
	}
}
signed main(void) {
    //freopen("m.in","r",stdin);
    //freopen("m.out","w",stdout);
	N=read();
	for(int i=1;i<=N;i++) {
		s[i]=read();l[i]=read();
		for(int j=1;j<=s[i];j++) {
			x[i][j]=read();
			y[i][j]=read();
		}
	}
	srand(time(NULL));
	tryy((1<<N)-1);
	printf("%lld\n",as);
/*	int s=N/2;
	for(int i=0;i<(1<<N);i++) {
		if(__builtin_popcount(i)!=s) continue;
		tryy(i);
	}
	if(N%2==1) {
		for(int i=0;i<(1<<N);i++) {
			if(__builtin_popcount(i)!=s+1) continue;
			tryy(i);
		}		
	}*/
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 53264kb

input:

3
3 50
300 2500
350 0
400 3000
2 120
380 0
400 2400
4 160
0 800
400 0
450 100
950 4600

output:

1460

result:

ok single line: '1460'

Test #2:

score: 0
Accepted
time: 8ms
memory: 53460kb

input:

4
2 160
384 0
1000 2464
3 280
0 2646
441 0
1000 2795
1 160
544 0
2 240
720 0
1220 2000

output:

2022

result:

ok single line: '2022'

Test #3:

score: 0
Accepted
time: 5085ms
memory: 94360kb

input:

11
6 192168
0 8547618
626988 33627138
706274 36560720
1103426 50858192
1399013 55291997
1418093 55559117
6 161415
0 58611901
321482 57647455
349707 57534555
550744 55524185
885629 50500910
1448846 27972230
6 195811
0 6825079
56106 8339941
78686 8836701
323216 12993711
525834 15627745
1414450 2095944...

output:

629407685

result:

ok single line: '629407685'

Test #4:

score: 0
Accepted
time: 5255ms
memory: 94300kb

input:

11
6 179446
0 62171637
917478 60336681
1352062 59032929
1368160 58566087
1370260 58503087
1473445 54375687
6 186773
0 2933427
20897 3748410
356883 13827990
1190424 27998187
1340354 29497487
1466118 29623251
6 185925
0 53735520
130212 51652128
582223 42611908
1090981 31419232
1380019 23326168
1466966...

output:

593944734

result:

ok single line: '593944734'

Test #5:

score: 0
Accepted
time: 5387ms
memory: 95968kb

input:

11
6 187590
0 512536
451768 16324416
582142 19714140
1060264 31667190
1212260 33491142
1463556 33742438
6 186786
0 39848792
254907 39084071
928124 31678684
1344556 21684316
1452774 18978866
1464360 18619700
6 177523
0 42981626
30401 42920824
495821 40593724
949343 37419070
1207056 33295662
1473623 2...

output:

568541879

result:

ok single line: '568541879'

Test #6:

score: 0
Accepted
time: 3150ms
memory: 78632kb

input:

11
6 180328
0 70912449
593492 69725465
631349 69119753
934610 63357794
1254206 51852338
1281827 50747498
2 1
543152 90245567
543162 90245567
6 176608
0 46706614
512238 65147182
604236 67263136
771264 69935584
987683 71666936
1285547 72858392
6 169123
0 71973961
349057 70228676
742671 63930852
106384...

output:

728555275

result:

ok single line: '728555275'

Test #7:

score: 0
Accepted
time: 3018ms
memory: 77408kb

input:

11
6 171004
0 62863146
53160 62703666
297997 60500133
928595 50410565
1047846 48383298
1196274 42891462
2 1
497649 90358616
497658 90358616
2 1
877017 61053965
877067 61053965
6 192851
0 73730741
188629 73542112
238857 72939376
589071 62432956
903490 52685967
1174427 43474109
6 165034
0 39275349
288...

output:

684905214

result:

ok single line: '684905214'

Test #8:

score: 0
Accepted
time: 3079ms
memory: 78348kb

input:

11
6 170701
0 66082360
363625 79900110
500001 84400518
1033901 98815818
1139446 99237998
1267187 99493480
2 1
529976 58976463
530026 58976463
6 199596
0 39595850
278702 34857916
365221 32781460
531968 28112544
917360 15009216
1238292 3455664
2 1
729627 23545904
729649 23545904
6 195425
0 21131820
63...

output:

539418869

result:

ok single line: '539418869'

Test #9:

score: 0
Accepted
time: 3062ms
memory: 77856kb

input:

11
2 1
731822 57736604
731847 57736604
6 177906
0 31265048
204117 29632112
367764 26686466
1053673 12282377
1153199 9694701
1266786 6059917
2 1
536410 26155530
536462 26155530
2 1
920218 89157371
920236 89157371
6 173499
0 5971470
368364 19969302
688960 30869566
1086522 43989112
1098619 44364119
127...

output:

615248718

result:

ok single line: '615248718'

Test #10:

score: 0
Accepted
time: 3040ms
memory: 77016kb

input:

11
6 196632
0 70110348
384388 82026376
394546 82199062
763377 86993865
810963 87422139
1260374 90118605
2 1
933046 16939393
933100 16939393
6 173665
0 25812347
235451 34524034
294814 36661102
403393 40352788
999221 58227628
1283341 59648228
6 177710
0 58412603
233394 55145087
426572 50122459
430534 ...

output:

735311761

result:

ok single line: '735311761'

Test #11:

score: 0
Accepted
time: 2098ms
memory: 66892kb

input:

11
2 1
327714 97173804
327766 97173804
6 174068
0 97264397
26713 97130832
179562 95143795
858948 81556075
987929 78460531
1015941 77704207
6 175212
0 64880924
252642 73976036
266800 74400776
390959 77132274
806405 81286734
1014797 82953870
6 163249
0 42044695
49476 41747839
197386 40120829
451676 35...

output:

558987902

result:

ok single line: '558987902'

Test #12:

score: 0
Accepted
time: 2042ms
memory: 67448kb

input:

11
6 163829
0 31289574
130497 30376095
712717 16402815
753079 15232317
797225 13907937
1066319 3144177
6 168138
0 63124751
45649 64585519
810233 88287623
898033 90658223
905417 90842823
1062010 91312602
6 170025
0 53069325
321981 48561591
591234 41291760
942888 31093794
1024294 28488802
1060123 2705...

output:

569257965

result:

ok single line: '569257965'

Test #13:

score: 0
Accepted
time: 2182ms
memory: 67264kb

input:

11
6 167138
0 51023002
165600 56984602
219698 58878032
339095 61146575
892576 71109233
1041644 72748981
2 1
689176 94343012
689249 94343012
6 178942
0 58650734
374 58663824
515755 76186778
947018 84812038
988564 85559866
1029840 85724970
6 173405
0 47201281
229648 55468609
308300 57434909
384679 588...

output:

675590982

result:

ok single line: '675590982'

Test #14:

score: 0
Accepted
time: 2108ms
memory: 67424kb

input:

11
6 174305
0 94317116
156381 93066068
738860 83163925
801318 81914765
1058316 74461823
1076858 73738685
6 187492
0 57378030
357720 70255950
383079 70940643
538696 74519834
830802 80946166
1063671 84439201
6 179318
0 62479756
269535 70565806
281413 70874634
634924 74763255
916720 75608643
1071845 75...

output:

712616989

result:

ok single line: '712616989'

Test #15:

score: 0
Accepted
time: 2026ms
memory: 67340kb

input:

11
6 181795
0 17122556
102744 21129572
299317 28009627
806065 45239059
921763 47553019
1095305 48420729
6 190533
0 42602682
10275 43003407
180188 48610536
865763 67806636
939173 69715296
1086567 71631418
2 1
529036 58707251
529083 58707251
2 1
917587 10593491
917630 10593491
6 166172
0 73743543
1369...

output:

542369675

result:

ok single line: '542369675'

Test #16:

score: 0
Accepted
time: 1559ms
memory: 60232kb

input:

11
2 1
727800 20498697
727829 20498697
6 177706
0 21250146
38893 21133467
250783 20285907
792887 8359619
798142 8191459
884652 5163609
6 162623
0 14906340
379619 30091100
415655 31424432
559643 35888060
746934 39821171
899735 42571589
6 179608
0 11941388
203734 19479546
321997 23263962
444492 265713...

output:

432748635

result:

ok single line: '432748635'

Test #17:

score: 0
Accepted
time: 1558ms
memory: 60044kb

input:

11
2 1
331882 64233485
331943 64233485
6 161328
0 26996144
322377 22805243
707171 16648539
771738 15357199
776897 15248860
867217 12448940
2 1
867971 91310630
867989 91310630
6 160555
0 78199529
86753 80715366
401127 88574716
504487 90848636
790264 95135291
867990 95290743
2 1
703673 27828123
703687...

output:

683878583

result:

ok single line: '683878583'

Test #18:

score: 0
Accepted
time: 1591ms
memory: 60136kb

input:

11
6 174316
0 47897162
641806 72927596
644242 73010420
755581 76016573
811250 76628932
893211 76792854
6 166188
0 66549903
71840 66406223
119861 65877992
325611 62791742
616567 54644974
901339 44393182
6 165579
0 1031241
48042 2760753
196253 5724973
535978 10820848
581549 11003132
901948 11964329
2 ...

output:

619086324

result:

ok single line: '619086324'

Test #19:

score: 0
Accepted
time: 1656ms
memory: 60496kb

input:

11
6 167704
0 58832679
370569 55868127
626169 53567727
663624 52781172
836807 47412499
898647 45309939
6 178808
0 88894906
243375 88164781
297907 87946653
335037 87315443
849159 75490637
887543 74032045
2 1
730898 45305194
730922 45305194
2 1
167710 57873219
167770 57873219
2 1
346582 81704091
34665...

output:

584549217

result:

ok single line: '584549217'

Test #20:

score: 0
Accepted
time: 1576ms
memory: 60052kb

input:

11
6 172855
0 42531672
172560 42186552
638982 36123066
740826 34697250
880888 31896010
912058 30960910
2 1
172859 87907354
172901 87907354
2 1
913759 84347576
913770 84347576
2 1
737496 15253290
737524 15253290
2 1
550983 60643609
551035 60643609
6 194108
0 64902863
18457 64810578
217247 61431148
54...

output:

597390225

result:

ok single line: '597390225'

Test #21:

score: 0
Accepted
time: 1085ms
memory: 54492kb

input:

11
2 1
531 70843885
615 70843885
2 1
343 58517596
443 58517596
2 1
215 65255473
306 65255473
2 1
1 85022551
78 85022551
2 1
308 25241720
339 25241720
2 1
451 26840810
529 26840810
2 1
209 65672580
210 65672580
2 1
658 10786993
725 10786993
2 1
139 59113224
207 59113224
2 1
88 31479467
130 31479467
2...

output:

529410596

result:

ok single line: '529410596'

Test #22:

score: 0
Accepted
time: 1128ms
memory: 54160kb

input:

11
3 10
11 10000000
12 0
13 10000000
3 20
21 10000000
22 0
23 10000000
3 40
41 10000000
42 0
43 10000000
3 80
81 10000000
82 0
83 10000000
3 160
161 10000000
162 0
163 10000000
3 320
321 10000000
322 0
323 10000000
3 640
641 10000000
642 0
643 10000000
3 1280
1281 10000000
1282 0
1283 10000000
3 256...

output:

0

result:

ok single line: '0'

Test #23:

score: -100
Time Limit Exceeded

input:

11
3 100000
100100 10000000
100101 0
100102 10000000
4 1
99999 10000000
100000 101022
201022 0
201023 10000000
4 2
99999 10000000
100000 0
201021 101021
201022 10000000
4 4
99999 10000000
100000 101019
201019 0
201020 10000000
4 8
99999 10000000
100000 0
201015 101015
201016 10000000
4 16
99999 1000...

output:


result: