QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#575116 | #5513. Advertisement 2 | ModyKachef | 23 | 0ms | 3876kb | C++23 | 1.2kb | 2024-09-19 10:38:55 | 2024-09-19 10:38:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int x[20] , e[20];
int ans =1e18 ;
void brute(int i , int msk , int cnt){
if (i == n){
if (msk == (1<<n)-1) ans = min(ans , cnt);
return;
}
brute(i+1 , msk , cnt);
int nmsk = msk;
for (int j = 0 ; j < n; j++){
if (abs(x[i]-x[j]) <= e[i]-e[j]) nmsk|=(1<<j);
}
brute(i+1 , nmsk , cnt+1);
}
bool adj[(int)1001][1001];
signed main(){
cin >> n;
vector<pair<int , int>> v(1);
for (int i = 1 ; i<= n; i++){
cin >> x[i] >> e[i];
v.push_back({e[i] , x[i]});
}
sort(v.begin()+1 , v.end() , greater<>());
for (int i = 1 ; i <= n ; i++){
e[i] = v[i].first;
x[i] = v[i].second;
}
for (int i = 1 ; i <= n ; i++){
for (int j = 1 ; j <= n ; j++){
if (abs(x[i] - x[j]) <= e[i] - e[j]) adj[i][j] = 1;
}
}
int ans = 0;
bool vis[(int)n+1] = {};
for (int i = 1 ; i <= n ; i++){
if (vis[i]) continue;
ans++;
for (int j = 1 ; j <= n ; j++){
if (adj[i][j]) vis[j] = 1;
}
}
cout << ans;
}
// | X[i] - X[j] | <= E[i]
详细
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
128800 9199612 51970557 152303663 51970557 658020283 51970557 305169975 51970557 647937895 51970557 162441995 51970557 664350717 51970557 128813867 51970557 815800777 51970557 422654970 51970557 5325941 51970557 919605369 51970557 775929588 51970557 957253076 51970557 441558150 51970557 730596606 51...
output:
result:
Subtask #2:
score: 23
Accepted
Test #9:
score: 23
Accepted
time: 0ms
memory: 3508kb
input:
3 231636235 354089104 228392707 930073348 587735804 575683740
output:
2
result:
ok single line: '2'
Test #10:
score: 23
Accepted
time: 0ms
memory: 3656kb
input:
2 44803615 325394921 960290812 913042209
output:
2
result:
ok single line: '2'
Test #11:
score: 23
Accepted
time: 0ms
memory: 3832kb
input:
16 358962202 959156048 292228464 457977429 286504790 688097514 10235865 287544591 543037593 223202351 281739475 678894125 340538778 135823278 523049160 699098750 632448464 27592532 678838907 280282008 232201876 610344934 372201424 580697311 534022553 149440684 396794335 231096472 386573567 674797431...
output:
1
result:
ok single line: '1'
Test #12:
score: 23
Accepted
time: 0ms
memory: 3796kb
input:
16 991478601 586353863 727677584 413218995 848190574 721774939 337154838 587621991 326181535 330546474 885714927 902337871 321925936 254469460 389203245 713455202 269046070 768322315 614176036 221983130 199199666 945777980 333801969 632191948 426251079 645513607 230568723 962651792 817646607 6209057...
output:
3
result:
ok single line: '3'
Test #13:
score: 23
Accepted
time: 0ms
memory: 3676kb
input:
16 259716405 81082178 865953834 204158972 701456061 326495636 534687353 313425011 649435476 973258810 655435866 100458236 842552753 181656857 473079491 116991153 2508936 173927847 405046133 391068638 302771733 495790124 35966251 515357032 272182509 442914085 348221691 938487780 990378664 943640991 2...
output:
3
result:
ok single line: '3'
Test #14:
score: 23
Accepted
time: 0ms
memory: 3872kb
input:
16 750613470 787418986 170979548 365164484 538034539 608096710 860751449 225707539 484373402 547435035 940351136 194668865 912301765 93898337 458896779 93991117 604496090 637207865 887366195 906979783 557233961 724709014 79115098 854994617 46404315 744331005 915505818 998759323 415682887 70000722 24...
output:
3
result:
ok single line: '3'
Test #15:
score: 23
Accepted
time: 0ms
memory: 3828kb
input:
16 4 4 12 10 7 1 14 9 5 1 7 4 6 2 11 12 11 8 7 7 1 16 1 7 7 11 10 1 5 9 16 14
output:
4
result:
ok single line: '4'
Test #16:
score: 23
Accepted
time: 0ms
memory: 3636kb
input:
16 14 11 15 15 2 2 9 11 12 3 1 2 5 6 3 8 11 6 6 8 16 8 7 13 14 15 3 9 11 13 5 12
output:
5
result:
ok single line: '5'
Test #17:
score: 23
Accepted
time: 0ms
memory: 3632kb
input:
16 658226792 613575956 913043019 676526283 924694003 969774080 131921851 969262560 105914395 172872671 871392287 24274699 165576907 264780282 21100418 923953766 624953565 298094995 530525465 571735572 303994035 463877704 809045037 954969312 573298570 667280152 101731595 308198144 530525465 554053924...
output:
4
result:
ok single line: '4'
Test #18:
score: 23
Accepted
time: 0ms
memory: 3572kb
input:
16 41059816 221337331 83624488 326689210 104858222 385883720 404619929 86122013 634866221 167428105 333552651 862965438 254015874 434293389 326707158 747676654 450873607 69675126 443566588 47175354 634866221 532361838 611136129 921561993 859951785 430454936 166920241 409984963 634866221 611154765 45...
output:
3
result:
ok single line: '3'
Test #19:
score: 23
Accepted
time: 0ms
memory: 3796kb
input:
16 936303273 104982189 63575875 559779062 796436147 569999950 688713338 829608600 54555214 355061353 213704891 195911676 392107461 17509106 922762043 308356453 301430216 797633403 991422839 48500064 287802278 121814289 172394178 237222389 688713338 135188143 633629597 30839372 564890892 276172238 68...
output:
2
result:
ok single line: '2'
Test #20:
score: 23
Accepted
time: 0ms
memory: 3580kb
input:
16 357789622 471544489 155990470 269745335 398736883 512491748 873381940 675455361 693445929 807200795 819730274 729107023 609830064 723584926 909092208 639745095 717541218 831296078 384480802 498235672 255651917 369406780 368140959 481895828 478227819 591982683 939144255 609693050 40813895 15456875...
output:
8
result:
ok single line: '8'
Test #21:
score: 23
Accepted
time: 0ms
memory: 3632kb
input:
16 675342555 193353548 971242060 11 536846016 331850093 836414885 32281218 186149471 245161906 928775073 8 750901538 117794571 828962292 39733819 911644130 4 588800258 279895844 296580159 355592604 802169978 66526131 273197350 332209795 404841833 463854267 109933975 168946414 885435693 10
output:
8
result:
ok single line: '8'
Test #22:
score: 23
Accepted
time: 0ms
memory: 3876kb
input:
16 953262221 724605861 954831951 723036137 687777113 990090964 350416397 707784111 683740929 986054786 599178111 901491972 585162338 898281936 692323709 985544379 525093723 882461438 557373498 914741210 584165982 899278291 203656094 561023816 854238442 823629640 278833052 636200772 577917599 8941971...
output:
11
result:
ok single line: '11'
Test #23:
score: 23
Accepted
time: 0ms
memory: 3864kb
input:
16 254025469 306467199 427159560 479601287 593614318 571659026 928541548 665993610 896411728 698123427 892481215 694192919 63151125 115592847 986723922 607811241 499586562 552028289 556415811 608857532 293855819 346297542 128409262 180850989 763105705 574193679 238718076 291159807 101875941 15431766...
output:
11
result:
ok single line: '11'
Subtask #3:
score: 0
Runtime Error
Dependency #2:
100%
Accepted
Test #24:
score: 0
Runtime Error
input:
969 40204287 456937654 286592935 721399309 55601488 988576547 98308463 233903868 372607004 249568606 671927697 865318354 859455683 411992226 204457272 180441733 613470249 214734085 527175838 697833267 358494964 102583786 46530087 943520460 253765364 851932504 364762894 237641176 205684131 478882150 ...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
0%