QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #828406 | #9913. 绝顶之战 | Hanghang | 100 ✓ | 266ms | 79892kb | C++20 | 833b | 2024-12-23 16:30:05 | 2024-12-23 16:30:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=15,M=(1<<14)+3,INF=1e18;
ll n,m,a[N],sum[M];
unordered_map<ll,ll>F[N][M];
ll Dfs(ll x,ll S,ll T)
{
if(x==n)return INF;
if(!(S>>x&1)&&a[x]<=sum[T])return -INF;
if(F[x][S].count(T))return F[x][S][T];
ll &s=F[x][S][T];s=-INF;
if(!(S>>x&1))return s=min(a[x],Dfs(x+1,S,T));
if(!(T>>x&1))return s=Dfs(x+1,S^(1<<x),T);
int now=T^(1<<x);S^=1<<x;
for(int v=now;;v=(v-1)&now)
{
s=max(s,Dfs(x+1,S,v)+Dfs(x+1,S,now^v));
if(!v)break;
}
return s+=a[x];
}
int main()
{
cin>>m>>n;set<ll>ans;
for(int i=0;i<n;i++)cin>>a[i];
for(int S=0;S<(1<<n);S++)sum[S]=sum[S^(S&-S)]+a[__builtin_ctz(S)];
for(int S=0;S<(1<<n);S++)if(sum[S]<=m&&m<Dfs(0,S,S))ans.insert(sum[S]);
cout<<ans.size()<<endl;
for(auto it:ans)cout<<it<<" ";
}
详细
Subtask #1:
score: 15
Accepted
Test #1:
score: 15
Accepted
time: 2ms
memory: 17004kb
input:
9 5 5 4 5 3 5
output:
3 5 8 9
result:
ok 4 number(s): "3 5 8 9"
Test #2:
score: 15
Accepted
time: 5ms
memory: 17012kb
input:
10 5 7 4 5 4 6
output:
1 7
result:
ok 2 number(s): "1 7"
Test #3:
score: 15
Accepted
time: 0ms
memory: 17232kb
input:
9 5 8 4 3 5 6
output:
1 8
result:
ok 2 number(s): "1 8"
Test #4:
score: 15
Accepted
time: 0ms
memory: 17236kb
input:
10 5 6 6 5 4 5
output:
2 6 10
result:
ok 3 number(s): "2 6 10"
Test #5:
score: 15
Accepted
time: 3ms
memory: 16956kb
input:
10 5 6 6 5 3 4
output:
2 6 9
result:
ok 3 number(s): "2 6 9"
Subtask #2:
score: 5
Accepted
Test #6:
score: 5
Accepted
time: 0ms
memory: 17012kb
input:
9146201596026093 2 1959292328727211 3046691025174768
output:
1 5005983353901979
result:
ok 2 number(s): "1 5005983353901979"
Test #7:
score: 5
Accepted
time: 0ms
memory: 17176kb
input:
9275681991750590 2 5186569060202341 3113841469169509
output:
2 5186569060202341 8300410529371850
result:
ok 3 number(s): "2 5186569060202341 8300410529371850"
Test #8:
score: 5
Accepted
time: 0ms
memory: 17188kb
input:
9401675366106951 2 149091771205127 6947611558612479
output:
2 149091771205127 7096703329817606
result:
ok 3 number(s): "2 149091771205127 7096703329817606"
Test #9:
score: 5
Accepted
time: 0ms
memory: 17196kb
input:
9392557811857168 2 160423759804827 7346645029161642
output:
2 160423759804827 7507068788966469
result:
ok 3 number(s): "2 160423759804827 7507068788966469"
Test #10:
score: 5
Accepted
time: 5ms
memory: 17012kb
input:
9822837057566509 2 108146351103958 7480790958348985
output:
2 108146351103958 7588937309452943
result:
ok 3 number(s): "2 108146351103958 7588937309452943"
Subtask #3:
score: 5
Accepted
Test #11:
score: 5
Accepted
time: 2ms
memory: 16952kb
input:
9107037180352846 3 2775941126614211 2097129959011760 1941377836547846
output:
2 4873071085625971 6814448922173817
result:
ok 3 number(s): "2 4873071085625971 6814448922173817"
Test #12:
score: 5
Accepted
time: 2ms
memory: 17192kb
input:
9356790767702598 3 5546180935211679 2905945428392309 1761953813389806
output:
2 7308134748601485 8452126363603988
result:
ok 3 number(s): "2 7308134748601485 8452126363603988"
Test #13:
score: 5
Accepted
time: 5ms
memory: 17200kb
input:
9850427814943989 3 142199778279844 6707702417646007 5098690319392154
output:
3 142199778279844 5240890097671998 6849902195925851
result:
ok 4 number(s): "3 142199778279844 5240890097671998 6849902195925851"
Test #14:
score: 5
Accepted
time: 0ms
memory: 17008kb
input:
9289721094295218 3 158922512595425 6720813049590970 5533326304480556
output:
3 158922512595425 5692248817075981 6879735562186395
result:
ok 4 number(s): "3 158922512595425 5692248817075981 6879735562186395"
Test #15:
score: 5
Accepted
time: 0ms
memory: 17008kb
input:
9089829946377332 3 153331859334767 6955566390185762 5391139066021841
output:
3 153331859334767 5544470925356608 7108898249520529
result:
ok 4 number(s): "3 153331859334767 5544470925356608 7108898249520529"
Subtask #4:
score: 5
Accepted
Test #16:
score: 5
Accepted
time: 5ms
memory: 17012kb
input:
9035514376902827 5 1861522865446152 1901640741231313 2239047273044626 2596933481542076 2408801444166990
output:
4 3763163606677465 6002210879722091 8411012323889081 8599144361264167
result:
ok 5 number(s): "4 3763163606677465 60022108797...11012323889081 8599144361264167"
Test #17:
score: 5
Accepted
time: 0ms
memory: 16952kb
input:
9720759307951601 5 5245904226180530 3078325181926984 1664005610640026 897140663439037 545770017429336
output:
5 7807050500259593 8324229408107514 8352820517688929 8869999425536850 9221370071546551
result:
ok 6 numbers
Test #18:
score: 5
Accepted
time: 0ms
memory: 16948kb
input:
9914984513811788 5 143280160480180 109619234770197 6890320393268943 5403376030977054 4137173786378446
output:
5 252899395250377 4390073181628823 5656275426227431 7143219788519320 9793449212605877
result:
ok 6 numbers
Test #19:
score: 5
Accepted
time: 5ms
memory: 17020kb
input:
9759176874761010 5 133219343571190 120466941665747 6704653967672701 5571405145717257 4167138211880141
output:
4 253686285236937 4420824497117078 5825091430954194 6958340252909638
result:
ok 5 number(s): "4 253686285236937 442082449711...25091430954194 6958340252909638"
Test #20:
score: 5
Accepted
time: 2ms
memory: 16924kb
input:
9525506737874968 5 148963131354572 158578418411159 6828452733024137 5381364252000234 4049653682935737
output:
4 307541549765731 4357195232701468 5688905801765965 7135994282789868
result:
ok 5 number(s): "4 307541549765731 435719523270...88905801765965 7135994282789868"
Subtask #5:
score: 5
Accepted
Test #21:
score: 5
Accepted
time: 2ms
memory: 17052kb
input:
9023163981511792 7 1910131726862762 2116561201938147 2221366112235172 2543084904983947 2627118050952859 1894287864736168 2673898998406780
output:
5 4026692928800909 5920980793537077 6248059041036081 8142346905772249 8791143946020028
result:
ok 6 numbers
Test #22:
score: 5
Accepted
time: 5ms
memory: 16936kb
input:
9201962815585483 7 5414508209828189 3093292941553917 1685274817103741 948835864411768 509817155946068 281984678231046 159476022063405
output:
11 8051060883172449 8490079591638149 8558436047289766 8667277173445511 8717912069353171 8789785829613152 8840420725520812 8949261851676557 8999896747584217 9017618307328174 9177094329391579
result:
ok 12 numbers
Test #23:
score: 5
Accepted
time: 5ms
memory: 16912kb
input:
9826610363201771 7 162505577758383 135338647957173 6721075735733948 5272016953171334 3778424372952824 2933545141068482 2192801947755330
output:
11 4076268598668380 5424191314539368 5569861178886890 6269070546423710 7009813739736862 7018919961449504 7762663126642220 8503406319955372 9202615687492192 9211721909204834 9348285551839714
result:
ok 12 numbers
Test #24:
score: 5
Accepted
time: 0ms
memory: 16968kb
input:
9130499502023512 7 155672196353335 159186169334854 143660830359863 7428948651751866 5151447515782955 3798505869621088 3051456865715739
output:
7 458519196048052 3509976061763791 4257025065669140 5609966711831007 7308481931384879 7887467847799918 8661423577546746
result:
ok 8 numbers
Test #25:
score: 5
Accepted
time: 0ms
memory: 17252kb
input:
9787957086564562 7 187238348793225 123717981911599 129684193048160 6696615131438344 5283070868135540 3906283631465365 2886113099800319
output:
8 440640523752984 3326753623553303 4346924155218349 5723711391888524 7137255655191328 7233037255018668 8609824491688843 9629995023353889
result:
ok 9 numbers
Subtask #6:
score: 5
Accepted
Test #26:
score: 5
Accepted
time: 6ms
memory: 17216kb
input:
9843534281138117 9 2077071368628181 2828099538983996 3196114494343630 3055890563571162 2057088847509186 2194463607939255 2091779370708588 3167995993737888 2800516708286895
output:
6 4905170907612177 6962259755121363 7961061471183339 8101285401955807 9054039125829951 9156723363060618
result:
ok 7 numbers
Test #27:
score: 5
Accepted
time: 6ms
memory: 17340kb
input:
9089321288577479 9 5013478738969552 3157961240306159 1653601571668037 995106965792662 547346063380849 294963106466152 160268607573676 93635792107328 51921499739784
output:
17 7815215379905378 8262976282317191 8515359239231888 8650053738124364 8678593193055323 8716686553590712 8758400845958256 8770707542396344 8772228985162651 8810322345698040 8864343334503672 8879054650230236 8930976149970020 8972690442337564 9013749149122712 9024611942077348 9065670648862496
result:
ok 18 numbers
Test #28:
score: 5
Accepted
time: 6ms
memory: 17296kb
input:
9228466779362818 9 138297550369877 130923331965746 6781722444706425 5322544847732556 4066738295445476 3069444036943107 2164702704009501 1770338045202555 1190140118936057
output:
23 5394401750483736 5503367623288231 5591765730068179 6500661881790600 6693507742224288 6781905849004236 7050943327042048 7273705668490786 7296437341919711 7362103775270734 7405403214724206 7690802000726657 7756468434077680 8241083445978105 8270999926993155 8463845787426843 8552243894206791 85955433...
result:
ok 24 numbers
Test #29:
score: 5
Accepted
time: 0ms
memory: 17096kb
input:
9212737112748513 9 183955156420715 137274489671458 114555376485976 6952502804268520 5522728516286281 4030640330044608 2854429096629358 2316695709170732 1632544471040460
output:
18 2068329493618609 3290214119207507 4385025202789341 4466425352622757 4922758590247967 5606909828378239 5958513538864430 6098969823663217 6783121061793489 7239454299418699 7320854449252115 7388287826846669 7591058009904890 8275209248035162 8415665532833949 8812942635493788 8953398920292575 90208322...
result:
ok 19 numbers
Test #30:
score: 5
Accepted
time: 5ms
memory: 17112kb
input:
9252713525210010 9 162740017680509 127023684986275 155152778412278 175338690039624 7412436877077191 5091441554206713 4090942515178659 3126367996844513 2202317580662331
output:
11 620255171118686 2822572751781017 3746623167963199 4711197686297345 5711696725325399 5948940748625530 6913515266959676 7837565683141858 7914014305987730 8032692048195877 8838064722169912
result:
ok 12 numbers
Subtask #7:
score: 10
Accepted
Test #31:
score: 10
Accepted
time: 0ms
memory: 17136kb
input:
9431564240371856 11 2072502046158126 2066316271517661 2163529290633843 2033552924777258 2060295112538633 2170963915845858 2830153069449699 2750192266102216 2436460356484587 2070428523960501 2346826281628005
output:
5 4138818317675787 6172371242453045 6302347608309630 8232666354991678 8335900533086888
result:
ok 6 numbers
Test #32:
score: 10
Accepted
time: 8ms
memory: 19804kb
input:
9748017886882097 11 5621106261846239 2963693598568387 1770987181252029 893130050604348 502107706153055 286239930406429 177406459478434 98736836706145 50305470562766 29068874911746 16153459380560
output:
35 8943134525148696 9159002300895322 9242710891860706 9267835771823317 9281172208128898 9346505394595606 9394936760738985 9445242231301751 9458578667607332 9468675301829182 9517106667972561 9567412138535327 9573457715874046 9595776290744850 9617012886395870 9621889082017425 9629928301927056 96431256...
result:
ok 36 numbers
Test #33:
score: 10
Accepted
time: 6ms
memory: 17384kb
input:
9729347332638556 11 163205101237135 138624963742945 7383174429729118 5444520240796106 4096476332219865 2816505442061853 2326400497103976 1738089722146197 1209769283839695 998817076886274 681867756759546
output:
60 6654505287985604 7182825726292106 7214811839261798 7336373044745150 7346165403185837 7427035139422006 7484440027922383 7637987346375427 7653322364871878 7685004494709198 7723523971190195 7864693483051652 7896679596021344 7934476178143616 7954936666502155 8028033159945383 8072750802880162 81663077...
result:
ok 61 numbers
Test #34:
score: 10
Accepted
time: 6ms
memory: 17508kb
input:
9562754215575569 11 161485396106512 149434616709912 146002147507153 7382000408536557 5057907834305831 4172105824491835 2954718800198612 2331161721531018 1679290402557369 1327100836040863 958505415004628
output:
46 4421818813926437 5514829994629408 5697247211567680 5742802682053207 5794475120452827 6049436778084186 6308318387372781 6418032199120421 6473335409634036 6701308097057835 6752980535457455 6841930830670271 6914634235860903 6960189706346430 7069903518094070 7194120397186777 7266823802377409 73765376...
result:
ok 47 numbers
Test #35:
score: 10
Accepted
time: 0ms
memory: 17284kb
input:
9194213030272623 11 151203400846131 124120452633619 125742788205690 163158396087644 7018622412796568 5193669265366797 4128466957224227 2835843673808823 2174592423658379 1749173457831955 1298726481658321
output:
30 1862951519431405 3400068711581907 3612124977263360 4037543943089784 4487990919263418 4692691994997311 4698795193240228 5149242169413862 5574661135240286 5757894303139881 5786717400921739 5991418476655632 6441865452829266 6447968651072183 6867284418655690 6873387616898607 7056620784798202 73238345...
result:
ok 31 numbers
Subtask #8:
score: 10
Accepted
Test #36:
score: 10
Accepted
time: 5ms
memory: 17284kb
input:
9205033666499013 12 2850462003249404 2805242660077069 2429054981777503 2963815386637346 2482550367349595 1986471485219802 2520994127845999 2437529223970625 2627469170446910 1921642320209105 2645728927620059 2290578758228158
output:
4 5655704663326473 7577346983535578 7642176148546275 8084759645103976
result:
ok 5 number(s): "4 5655704663326473 75773469835...42176148546275 8084759645103976"
Test #37:
score: 10
Accepted
time: 26ms
memory: 24264kb
input:
9312008144548179 12 5098312777552324 2828210584202914 1698846116084863 972763022136388 536323112196116 296239601985823 168374174447656 95736456798989 55681139272124 31357956485449 16061655649327 9384457843970
output:
37 8442757358256913 8599358804238576 8682840868467206 8810706296005373 8839442314448869 8883344013654040 8923399331180905 8967307741987036 8979080470453029 9039945459635703 9080000777162568 9104323959949243 9107508049941485 9124464628318028 9135681916434692 9180145767590152 9188843128631568 92202010...
result:
ok 38 numbers
Test #38:
score: 10
Accepted
time: 3ms
memory: 18012kb
input:
9156085216063046 12 123047715954567 102070372364803 6915592549395858 5255619619792358 3803494030028777 3144753698528503 2201976837739733 1637371070914506 1246360406659115 942243938371027 740235765048371 549861629651347
output:
92 5860688033284071 6253070342003751 6600923798332442 6780450585739227 6802931971655098 6912343595921768 6970824721136251 6993306107052122 7118108779026234 7140710637715228 7172832894458907 7173365816876650 7209219695502112 7276959744422190 7368070660898068 7462205225573115 7467333879819214 74769493...
result:
ok 93 numbers
Test #39:
score: 10
Accepted
time: 3ms
memory: 17736kb
input:
9286877881168289 12 160985053204177 100889151079338 118274510570377 7069745807992134 5000997579129201 4029329896631094 2864807840694241 2289538705919012 1777932458904240 1314987331906972 995766127923476 716515790394942
output:
75 5185350423983522 5534495261467145 5762607211584116 6097662084378035 6121760529803404 6251011051862087 6272225805773523 6337876346359345 6376912421906569 6479123001979058 6530261389390621 6696133625890065 6699017317403998 6720232071315434 6735170932770791 6758373339507592 6849482593374117 69039268...
result:
ok 76 numbers
Test #40:
score: 10
Accepted
time: 0ms
memory: 17776kb
input:
9418852853476875 12 160943007964367 114061835195663 176210220688578 150735166859030 6891091613133140 5165951633912061 4103315397738327 2853067598258136 2133396328555547 1588140275356272 1272833769324109 954169504156861
output:
52 4409187333122635 4417093779544880 4705265628445965 4962349832744155 5043158104322046 5277656338776318 5588414157521321 5596320603943566 5659435132602826 5682021102446744 5767901864619699 5978099397770074 5997327608478907 6293405903802237 6315991873646155 6542583661678182 6550490108100427 67220713...
result:
ok 53 numbers
Subtask #9:
score: 10
Accepted
Test #41:
score: 10
Accepted
time: 2ms
memory: 17152kb
input:
9386101775874151 13 2988434015746527 2531638596517047 2952017129004226 2532501379103299 2134686632728924 2723134092613376 2734705006477432 2790707225133977 2417142090510094 2242777209869653 2707931539021407 2508571481588074 2833570313484694
output:
4 5520072612263574 7654759244992498 8052573991366873 8472089741267800
result:
ok 5 number(s): "4 5520072612263574 76547592449...52573991366873 8472089741267800"
Test #42:
score: 10
Accepted
time: 73ms
memory: 37320kb
input:
9168182173116105 13 5245945745965630 2966339978381958 1587236525258288 896003981667415 529285939890159 293959638682944 169587396142065 91544716767044 52705601201500 28282607177863 17370633326495 9113216610963 5470267979344
output:
47 8397220330779551 8632546631986766 8756918874527645 8834961553902666 8873800669468210 8880319802235806 8926506270669710 8946058707300956 8971395785474477 9024101386675977 9034657895063658 9062940502241521 9067485420837493 9069992862938663 9087363496265158 9095768028015356 9098275470116526 91028203...
result:
ok 48 numbers
Test #43:
score: 10
Accepted
time: 0ms
memory: 19184kb
input:
9057590705040874 13 151011953297210 112937500100650 6954919394015031 5062352179161196 3815983297509558 3126023905930434 2249688509846560 1606614540509250 1331414287762336 940065801496011 748705768812574 537296788419311 380554154424067
output:
152 6369517734359384 6772286747436084 6929029381431328 6992858344215008 7017961579179004 7118223503171958 7140438361824591 7205956656837852 7246276409684104 7247472203597356 7269687062249989 7309583535855395 7313470327492373 7328433439483439 7395627357291708 7398515733603071 7458881183990619 7470212...
result:
ok 153 numbers
Test #44:
score: 10
Accepted
time: 7ms
memory: 19236kb
input:
9619853795254822 13 123940431155178 162523711925177 107836462048994 6822700253051457 5110099783287416 3993769630411792 2822763488731126 2324031368049785 1695643316370434 1295651412485787 939710327079122 674861198331984 548210539311153
output:
138 5548377398707829 6649337029114477 6727472126059902 6756569362027849 6764167199553397 6836746874396047 6883220021048680 6932698439678492 7023423878990697 7029016328300535 7118971913827871 7148069149795818 7155666987321366 7197547568425630 7200043704787199 7210833724272267 7217000858180806 7236738...
result:
ok 139 numbers
Test #45:
score: 10
Accepted
time: 10ms
memory: 18680kb
input:
9094111600491530 13 178514495805351 122750393534379 135571772562715 162034642144949 7440292597150722 5258981516523551 3938563464831610 3146933401183460 2194471923283433 1625843683248980 1284778875204505 917668548168702 677621406255024
output:
79 5096808316834831 5104783816924605 5215056175134028 5336855458748509 5341094659654580 5455103317047706 5673412056959058 5703965785784312 5822213644083509 5857852820570945 5940276628514287 5948252128604061 6014476865003533 6049269794734858 6132724723302730 6163278452127984 6289316936648536 63815871...
result:
ok 80 numbers
Subtask #10:
score: 30
Accepted
Test #46:
score: 30
Accepted
time: 5ms
memory: 17172kb
input:
9001324849976175 14 2825925335672803 2025589127489736 2269614904415361 1837491879093462 2158539836494236 2426078823971452 1924825856346157 2746394845754343 2268412247933575 2230951690565408 2494052463977166 2855920747842645 2234733913430870 2001499177846439
output:
6 4851514463162539 6689006342256001 7121129367577900 8613832198602158 8847546178750237 8958621246671362
result:
ok 7 numbers
Test #47:
score: 30
Accepted
time: 266ms
memory: 79892kb
input:
9972282568532949 14 5505337530293470 3041608956429561 1641948100087404 921229203322626 522006830353828 305104880869052 169979965880291 98139538460294 50438074200129 30572008666021 16022716436664 9778663336212 5597214430013 3030746040166
output:
52 8757178642022342 8974080591507118 9235610295041873 9279185472376170 9452512244526649 9587637159515410 9659477586935407 9681754651615156 9707179051195572 9753595079035153 9757617125395701 9801296543295318 9821162608829426 9838281919823785 9851734617495447 9858147985357893 9888719994023914 99058494...
result:
ok 53 numbers
Test #48:
score: 30
Accepted
time: 22ms
memory: 23520kb
input:
9877937388443765 14 155139073079805 192862804676552 6806108942076213 5245896845236199 4193284860015225 3002460316465341 2143868561800123 1606991113767718 1220674924610279 943181275066159 712121250581614 551168141337758 416543701493792 305015894176241
output:
290 7822881465459572 7957505905303538 7963202849874500 8090512371819612 8117345124501144 8118459014547394 8209355097036017 8210846118358225 8265306649906956 8292146413339423 8321996794399818 8349519039031939 8364611261708911 8370308206279873 8374049606797330 8379746551368292 8394838774045264 8399931...
result:
ok 291 numbers
Test #49:
score: 30
Accepted
time: 17ms
memory: 22136kb
input:
9698779026620385 14 111336434896272 188968958762314 172390777732351 6879371410753784 5584703661615821 4111954905991598 2962125259888879 2270422307171704 1694448142170312 1279776439750139 994321507927638 714237103436550 546621373757831 393878540328270
output:
215 6645743652537621 6657842974569193 6711664568410730 7093443786707428 7105543108739000 7219599133638948 7233709602832824 7248951924882509 7258285942168561 7349545927286368 7359980755974171 7372080078005743 7378898718529929 7399691880621832 7403367521127905 7413802349815708 7425901671847280 7517161...
result:
ok 216 numbers
Test #50:
score: 30
Accepted
time: 14ms
memory: 21384kb
input:
9182748968413255 14 141402162156562 94573479344637 151517728050441 96368330731367 7461111129477136 5135721991058416 3905278048306332 2990284418172774 2195118977230594 1771226774856121 1287639082550956 914596520830196 747678572446199 506726756463986
output:
137 3940502632574344 5628894853340952 5643147968196162 5643545077499524 5704612781279907 5711729407430465 5737846534920678 5871530729663904 6112482545646117 6126310447805409 6135621609804938 6175991852150361 6183108478300919 6183505587604281 6244573291384664 6416943668132574 6424060294283132 6485525...
result:
ok 138 numbers