QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#44116	#1833. Deleting	xiaoyaowudi	TL	3024ms	49872kb	C++14	730b	2022-08-13 08:17:33	2022-08-13 08:17:34

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-08-13 08:17:34]
评测

测评结果：TL
用时：3024ms
内存：49872kb

查看

[2022-08-13 08:17:33]
提交

answer

#include <iostream>
#include <algorithm>
#include <bitset>
constexpr int N=4010;
std::bitset<(N>>1)> f[N];int n,cst[N][N];
bool solve(int mid){
	for(int i=1;i<=n;++i) f[i].reset();
	for(int i=2;i<=n;++i){
		for(int j=2;j<=i;j+=2){
			if(cst[i-j+1][i]<=mid && (j==2 || (j!=2 && f[i-1][(j>>1)-1]))) f[i][j>>1]=true;
			if(f[i][j>>1]) f[i]|=(f[i-j]<<((j>>1)));
		}
	}
	return f[n][n>>1];
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin>>n;
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;j+=2)
			std::cin>>cst[i][j];
	}
	int l=1,r=(n/2)*(n/2),mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(solve(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	std::cout<<ans<<std::endl;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 3472kb

input:

2
1

output:

result:

ok 1 number(s): "1"

Test #2:

score: 0

Accepted

time: 2ms

memory: 3624kb

input:

output:

result:

ok 1 number(s): "6"

Test #3:

score: 0

Accepted

time: 2ms

memory: 3624kb

input:

10
20 21 2 11 25
3 24 18 8
6 17 7 5
22 4 23
14 15 1
19 16
12 10
13
9

output:

result:

ok 1 number(s): "14"

Test #4:

score: 0

Accepted

time: 1ms

memory: 3672kb

input:

16
49 48 18 41 52 64 4 6
22 20 32 50 56 36 9
3 1 27 58 51 35 40
61 43 38 12 7 34
8 59 39 25 46 16
44 29 15 17 24
10 47 2 57 62
14 5 23 33
30 45 19 60
63 28 13
54 55 26
53 31
11 42
21
37

output:

result:

ok 1 number(s): "30"

Test #5:

score: 0

Accepted

time: 2ms

memory: 3684kb

input:

20
91 19 90 92 5 41 15 50 18 36
97 8 23 74 53 67 83 40 26
4 16 31 82 80 28 49 6 21
58 63 70 34 27 89 68 20
55 100 35 77 52 24 11 87
94 13 66 1 32 54 86
60 79 75 93 45 73 2
48 72 12 37 29 95
56 17 44 84 30 22
14 65 76 69 62
47 78 7 57 42
39 61 99 81
88 25 98 59
85 38 10
33 51 71
64 46
43 3
96
9

output:

result:

ok 1 number(s): "54"

Test #6:

score: 0

Accepted

time: 1ms

memory: 4044kb

input:

100
750 481 1065 911 1943 427 1633 45 1841 234 1376 1075 1603 1682 1581 1284 28 5 1567 1540 2409 1430 695 667 1246 392 1183 1090 594 1481 524 2023 354 778 584 827 1516 796 1675 1829 189 1688 706 1679 1483 1010 1209 1393 399 210
40 149 1040 351 1435 320 340 577 898 449 1896 224 2168 1456 1222 1216 19...

output:

result:

ok 1 number(s): "1289"

Test #7:

score: 0

Accepted

time: 3ms

memory: 3944kb

input:

100
561 1112 852 529 2112 323 265 2038 1970 1681 556 2261 887 277 1171 553 1887 48 2432 266 1304 1764 853 2205 2320 1532 571 1870 193 544 1135 874 2132 1162 102 2179 2307 2068 1990 1111 2420 2077 1779 2000 1996 2297 1981 450 1091 992
140 2474 744 537 42 1051 1086 1685 1307 1282 2387 167 31 1179 301 ...

output:

result:

ok 1 number(s): "1082"

Test #8:

score: 0

Accepted

time: 141ms

memory: 9792kb

input:

1000
168625 248587 13361 216812 183629 130592 94183 152417 64237 66548 133370 190254 121255 46138 62441 214340 158394 100935 199720 242242 28785 185956 49195 170727 64011 159665 14265 193684 148792 234339 35901 173675 21572 54311 108353 180276 8738 219185 221308 163715 86748 23949 144379 9144 66996 ...

output:

result:

ok 1 number(s): "100069"

Test #9:

score: 0

Accepted

time: 540ms

memory: 19948kb

input:

2000
629753 453642 891406 271214 387757 205701 185083 533150 543744 346137 296803 8558 894334 685905 530329 660631 215508 749020 272754 548476 388081 623465 444491 267448 890422 788334 439713 48112 46778 39381 526152 419546 857234 306443 430102 627368 891680 622422 4172 521593 904148 871179 212505 4...

output:

result:

ok 1 number(s): "382553"

Test #10:

score: 0

Accepted

time: 1677ms

memory: 33852kb

input:

3000
780886 1272177 1981093 155764 1004024 2161066 2163860 1999899 1724418 2201045 1323203 386344 488844 98545 509647 660171 1911299 406766 566172 354749 65644 2064030 227791 613327 1446376 959116 1172810 2054662 479633 1239569 2070554 342062 1473376 1014363 1180623 1537364 2000637 903391 1796402 40...

output:

result:

ok 1 number(s): "855449"

Test #11:

score: 0

Accepted

time: 1795ms

memory: 33748kb

input:

3000
2151832 2040056 1820723 1647821 1989057 1438174 197301 2013861 1084109 1533178 1103873 1079635 1122200 380122 1741860 642218 137487 931199 98296 60463 929185 6804 2227061 1415272 1354710 2247351 2071905 1384180 589332 342057 411231 1069014 1813211 547349 1357495 1279819 209870 697345 849679 579...

output:

result:

ok 1 number(s): "871233"

Test #12:

score: 0

Accepted

time: 2235ms

memory: 33928kb

input:

3000
586185 739549 1512231 1576382 2124572 849993 259309 831983 1334988 1451320 838166 1344126 1721886 2217163 1041397 3821 1616533 942750 121005 2151935 661341 1751969 903062 1195769 1060979 893206 2162517 1129906 120059 1497730 286110 972028 269871 1670619 820006 1345011 950494 1701096 840150 9661...

output:

result:

ok 1 number(s): "865389"

Test #13:

score: 0

Accepted

time: 1794ms

memory: 33940kb

input:

3000
1838973 959493 468493 927886 325485 2015622 357872 2200246 1739668 76441 583587 578097 232536 268705 165522 1089532 2059535 233795 870754 1087324 1657808 22588 209194 1608421 326009 294431 1477964 789126 1280065 285509 1271181 1878718 1389793 35287 1120513 866529 1616607 176594 113345 2153274 1...

output:

result:

ok 1 number(s): "857976"

Test #14:

score: 0

Accepted

time: 1545ms

memory: 33944kb

input:

3000
2086761 540330 271330 2008226 990669 2021055 1090954 675002 1458191 1923206 946292 462231 1507637 397979 1156215 1492372 680422 1684765 1481640 1319997 338590 1945324 780771 398966 679166 297644 1204407 814416 195896 149004 837831 344985 939834 1594285 833326 135053 995307 151940 1280365 130315...

output:

result:

ok 1 number(s): "887030"

Test #15:

score: 0

Accepted

time: 3024ms

memory: 49872kb

input:

4000
1898521 2797950 963899 3568439 2519564 1914791 3738898 2159691 3247655 2698362 3974995 1182541 2046569 2815025 699396 227205 999269 1909823 2956594 3628363 2431691 92591 2797302 1413639 762460 1804303 3044744 3414120 3827117 814343 2913293 3505010 3893338 3738481 274918 1801763 646495 2013403 1...

output:

result:

ok 1 number(s): "1530061"

Test #16:

score: -100

Time Limit Exceeded

input:

4000
401966 1123581 1483128 1015860 899861 1782096 363484 250066 48695 674899 2230114 3502283 150698 1377108 976341 3346711 3027103 82354 295204 2806448 2155765 3517266 726926 1877590 3777786 98729 522034 1962443 2505254 2271688 2373070 3865631 2324550 1512900 2831294 1994732 3353955 1605618 2499103...