QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #518961 | #1833. Deleting | The_Shadow_Dragon | TL | 489ms | 20844kb | C++14 | 1.3kb | 2024-08-14 14:47:10 | 2024-08-14 14:47:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define sort stable_sort
#define endl '\n'
int cost[4010][4010];
bitset<4010>f[4010];
bool check(int lastmid,int mid,int n)
{
if(mid>lastmid)
{
for(int len=2;len<=n;len+=2)
{
for(int l=1,r=l+len-1;r<=n;l++,r++)
{
f[l][r]=(f[l+1][r-1]&(cost[l][r]<=mid));
for(int k=l+1;k<=r-1;k+=2)
{
if(f[l][r]==0)
{
f[l][r]=f[l][k]&f[k+1][r];
}
else
{
break;
}
}
}
}
}
else
{
for(int i=1;i<=n;i++)
{
f[i].reset();
f[i][i-1]=1;
}
for(int len=2;len<=n;len+=2)
{
for(int l=1,r=l+len-1;r<=n;l++,r++)
{
f[l][r]=(f[l+1][r-1]&(cost[l][r]<=mid));
for(int k=l+1;k<=r-1;k+=2)
{
if(f[l][r]==0)
{
f[l][r]=f[l][k]&f[k+1][r];
}
else
{
break;
}
}
}
}
}
return (f[1][n]==1);
}
int main()
{
int n,i,j,l=1,r,lastmid,mid,ans=0;
scanf("%d",&n);
lastmid=r=n*n/4;
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j+=2)
{
scanf("%d",&cost[i][j]);
}
}
while(l<=r)
{
mid=(l+r)/2;
if(check(lastmid,mid,n)==true)
{
ans=mid;
r=mid-1;
}
else
{
l=mid+1;
}
lastmid=mid;
}
printf("%d\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5964kb
input:
2 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 6020kb
input:
6 2 1 3 4 5 6 7 8 9
output:
6
result:
ok 1 number(s): "6"
Test #3:
score: 0
Accepted
time: 1ms
memory: 6032kb
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:
14
result:
ok 1 number(s): "14"
Test #4:
score: 0
Accepted
time: 1ms
memory: 8028kb
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:
30
result:
ok 1 number(s): "30"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5968kb
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:
54
result:
ok 1 number(s): "54"
Test #6:
score: 0
Accepted
time: 1ms
memory: 8012kb
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:
1289
result:
ok 1 number(s): "1289"
Test #7:
score: 0
Accepted
time: 2ms
memory: 6084kb
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:
1082
result:
ok 1 number(s): "1082"
Test #8:
score: 0
Accepted
time: 489ms
memory: 20844kb
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:
100069
result:
ok 1 number(s): "100069"
Test #9:
score: -100
Time Limit Exceeded
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...