QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #518007 | #6308. Magic | DaiRuiChen007 | TL | 1718ms | 7156kb | C++17 | 593b | 2024-08-13 15:09:14 | 2024-08-13 15:09:14 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
bitset <MAXN> G[MAXN];
int n,ans,L[MAXN],R[MAXN],tar[MAXN]; bool vis[MAXN];
bool dfs(int u) {
for(int v=1;v<=n;++v) if(G[u][v]&&!vis[v]) {
vis[v]=true;
if(!tar[v]||dfs(tar[v])) return tar[v]=u,true;
}
return false;
}
signed main() {
scanf("%d",&n),ans=2*n;
for(int i=1;i<=n;++i) scanf("%d%d",&L[i],&R[i]);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(L[i]<L[j]&&L[j]<R[i]&&R[i]<R[j]) G[j].set(i);
for(int i=1;i<=n;++i) memset(vis,false,sizeof(vis)),ans-=dfs(i);
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
5 2 3 6 7 1 9 5 10 4 8
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: 0
Accepted
time: 82ms
memory: 6932kb
input:
5000 7985 7987 42 46 1591 1593 407 410 6305 6306 1456 1457 5874 5875 7135 7137 7041 7046 6813 6815 8868 8871 665 666 4055 4056 9789 9796 7067 7068 4745 4746 5167 5171 1735 1737 2125 2128 1444 1447 1348 1352 6087 6090 1381 1384 1600 1601 5187 5190 2801 2802 8449 8450 9376 9377 4021 4024 2674 2676 490...
output:
8134
result:
ok 1 number(s): "8134"
Test #3:
score: 0
Accepted
time: 90ms
memory: 6992kb
input:
5000 3171 3172 4062 4064 4647 4651 3670 3673 7112 7114 9714 9717 3781 3789 8422 8426 457 460 5450 5454 7113 7122 6313 6320 9969 9973 828 832 6878 6892 4476 4483 892 903 251 259 6304 6315 130 134 9206 9215 2679 2686 9090 9091 8222 8228 9374 9375 2985 2989 3397 3401 4916 4918 6819 6821 883 889 2516 25...
output:
7047
result:
ok 1 number(s): "7047"
Test #4:
score: 0
Accepted
time: 107ms
memory: 7016kb
input:
5000 7269 7286 1979 1990 4225 4241 7866 7872 2052 2067 1508 1514 2366 2370 3488 3493 8979 8987 302 306 6730 6732 7704 7705 5528 5544 7420 7425 4705 4712 593 601 6662 6668 5228 5257 2008 2013 548 562 7949 7950 1017 1020 1025 1028 6 11 4722 4736 9945 9950 8368 8379 6781 6787 4558 4566 400 404 858 864 ...
output:
6191
result:
ok 1 number(s): "6191"
Test #5:
score: 0
Accepted
time: 167ms
memory: 7080kb
input:
5000 3005 3008 7811 7821 2832 2840 9812 9818 3947 3952 3629 3665 7443 7455 1473 1478 1467 1494 5499 5508 229 232 9477 9498 9500 9514 4769 4775 9488 9503 1514 1520 5101 5112 2455 2456 3558 3610 9072 9188 659 666 2286 2301 9735 9782 5959 5984 5823 5844 1827 1835 3658 3681 3494 3503 1016 1018 3418 3420...
output:
5636
result:
ok 1 number(s): "5636"
Test #6:
score: 0
Accepted
time: 483ms
memory: 7156kb
input:
5000 1017 1019 5731 5744 8592 8697 3414 3561 277 356 4421 4458 7969 7989 3733 3759 1975 1986 6895 6898 8580 8657 2320 2325 6494 6510 3574 3616 7721 7780 7756 7835 1744 1748 5085 5102 5428 5588 6823 6847 9348 9405 1969 2064 1152 1242 3676 3679 5569 5713 213 248 8277 8285 3739 3782 5582 5604 9076 9105...
output:
5225
result:
ok 1 number(s): "5225"
Test #7:
score: 0
Accepted
time: 1718ms
memory: 7156kb
input:
5000 4269 4768 7697 7804 4289 4316 6641 6742 3782 3871 9785 9858 1845 1979 6300 6412 8194 8616 3 18 8536 8790 7 129 4406 4448 3556 3609 2800 2918 3081 3164 1854 1948 8220 8546 7070 7318 1117 1195 8770 8944 5754 5760 8512 8590 5714 5829 6132 6156 8252 8381 889 1149 1899 1949 4675 4683 4282 4426 2977 ...
output:
5124
result:
ok 1 number(s): "5124"
Test #8:
score: -100
Time Limit Exceeded
input:
5000 1247 1337 3192 3474 7887 8008 2912 3065 4356 4573 9268 9376 987 1165 6972 7155 580 668 331 718 455 640 4815 4854 3783 3988 8426 8579 7459 7563 1991 2482 9585 9973 7562 7627 7472 8428 86 320 8319 8331 8596 8953 5729 6468 7209 7364 1026 1246 6575 6608 5048 5050 1957 2531 9408 9489 3092 3096 845 1...