QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#223794 | #7064. Spy | veg# | AC ✓ | 109ms | 7944kb | C++14 | 2.6kb | 2023-10-22 17:14:48 | 2023-10-22 17:14:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define re register
#define rint re int
#define ll long long
#define rll re ll
#define db double
#define rdb re db
#define rch re char
template <typename T> inline T read()
{
re T ans=0;rint f=0;rch ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=1;
for(;isdigit(ch);ch=getchar()) ans=ans*10+(ch&15);
return f?-ans:ans;
}
const int maxn=5e2+10;
const int maxm=4e5+10;
const ll Inf=0x3f3f3f3f3f3f3f3f;
struct Node
{
int to,next,val;
}e[maxm];
int head[maxn];
bool vis1[maxn];
bool vis2[maxn];
ll num1[maxn];
ll num2[maxn];
int bel1[maxn];
int bel2[maxn];
int pre[maxn];
ll mn[maxn];
int cnt,n;
inline void add(rint x,rint y,rint z)
{
e[++cnt].to=y;
e[cnt].next=head[x];
e[cnt].val=z;
head[x]=cnt;
}
inline void modify(rint x)
{
for(rint tmp2=x,tmp1=pre[x];tmp2;tmp1=pre[tmp2])
bel2[tmp2]=tmp1,swap(bel1[tmp1],tmp2);
}
inline void bfs(rint s)
{
memset(vis1+1,0,n),memset(vis2+1,0,n),memset(mn+1,0x3f,n<<3);
queue<int> q;q.push(s);
while(1)
{
while(!q.empty())
{
rint x=q.front();q.pop();vis1[x]=1;
for(rint i=head[x];i;i=e[i].next)
{
rint v=e[i].to;if(vis2[v]) continue;
if(num1[x]+num2[v]-e[i].val<mn[v])
{
mn[v]=num1[x]+num2[v]-e[i].val,pre[v]=x;
if(!mn[v])
{
vis2[v]=1;
if(!bel2[v]) return modify(v);
else q.push(bel2[v]);
}
}
}
}
rll tmp=Inf;
for(rint i=1;i<=n;i++) if(!vis2[i]) tmp=min(tmp,mn[i]);
for(rint i=1;i<=n;i++)
{
if(vis1[i]) num1[i]-=tmp;
if(vis2[i]) num2[i]+=tmp;
else mn[i]-=tmp;
}
for(rint i=1;i<=n;i++)
if(!vis2[i]&&!mn[i])
{
vis2[i]=1;
if(!bel2[i]) return modify(i);
else q.push(bel2[i]);
}
}
}
struct A{ll a; int p;}a[maxn];
bool cmp(A i,A j) {
return i.a<j.a;
}
ll b[maxn],c[maxn];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%lld",&a[i].a);
for(int i=1;i<=n;++i) scanf("%d",&a[i].p);
for(int i=1;i<=n;++i) scanf("%lld",&b[i]);
for(int i=1;i<=n;++i) scanf("%lld",&c[i]);
sort(c+1,c+n+1);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i) {
int l=0; ll s=0;
for(int j=1;j<=n;++j) {
while(l<=n&&a[l+1].a<b[i]+c[j]) {
++l;
s+=a[l].p;
}
add(i,j,s);
}
}
memset(num1+1,0xc0,n<<3);
for(rint x=1;x<=n;x++)
for(rint i=head[x];i;i=e[i].next)
num1[x]=max(num1[x],(ll)e[i].val);
for(rint i=1;i<=n;i++) bfs(i);
rll ans=0;
for(rint i=1;i<=n;i++) ans+=num1[i]+num2[i];
printf("%lld\n",ans);
// for(rint i=1;i<=n;i++) printf("%d ",bel2[i]);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3812kb
input:
4 1 2 3 4 1 1 1 1 0 0 1 1 0 1 1 2
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 6424kb
input:
400 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000...
output:
160000
result:
ok single line: '160000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
40 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 10000000000000000...
output:
1600
result:
ok single line: '1600'
Test #4:
score: 0
Accepted
time: 2ms
memory: 7272kb
input:
400 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000000000000 4000000...
output:
160000
result:
ok single line: '160000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7588kb
input:
400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -400 -...
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 7368kb
input:
400 41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 ...
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 2ms
memory: 7384kb
input:
400 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
400
result:
ok single line: '400'
Test #8:
score: 0
Accepted
time: 2ms
memory: 6752kb
input:
400 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1000000000000000000 -1...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
10 7 7 7 7 7 7 7 7 7 7 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 4 4 4 4 3
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
2 0 1 1 1 0 1 0 2
output:
3
result:
ok single line: '3'
Test #11:
score: 0
Accepted
time: 60ms
memory: 7236kb
input:
400 13847081798897 874663680339 -1528662074038 10439909774959 1822373103148 -6974433017907 6309247250385 11141586625400 16517676644164 -17331800423448 18505534619011 -19766744660346 6180770287595 10091989087414 568941650316 -16088179604413 4394384705024 -12261134024334 5922925172362 -15877810472552 ...
output:
84539
result:
ok single line: '84539'
Test #12:
score: 0
Accepted
time: 53ms
memory: 6180kb
input:
400 15303324246439 -3723332555981 13456786049020 -5449703381253 14800811164417 14869669832774 -8935406726744 17188618255567 -969955969860 -9782415306754 313401398018 -11039462554654 14986021405358 -14416653774872 8383500342130 -10016955880319 -7595947546269 5157260185522 -1603222670917 -337442035105...
output:
77070
result:
ok single line: '77070'
Test #13:
score: 0
Accepted
time: 55ms
memory: 7104kb
input:
400 -11778519553085 -16255960948010 -6226670878843 13615009183139 14247722110483 -13760764644121 17257861091111 -382049751137 -18229549564421 -4676037861677 16604678606012 13384796753704 4798803674372 -18237959122017 -17890402024503 11526905501044 -5896272864489 15870583446522 -16438263365549 -14109...
output:
88826
result:
ok single line: '88826'
Test #14:
score: 0
Accepted
time: 56ms
memory: 6756kb
input:
400 -5060891419563 11194603021718 7518136467372 10357185701947 3989891421036 8420213756689 2761846713999 -15866137191314 14511434162949 -13547972272308 -11341077208438 1850394936472 6759473618586 -17545628892952 -136933759604 -15416862622640 -1971715904134 -13646627103589 13279907642860 -18895466094...
output:
83447
result:
ok single line: '83447'
Test #15:
score: 0
Accepted
time: 57ms
memory: 6136kb
input:
400 16919086217506 -6384989605958 -13202792652870 -7863676941990 3731048765018 -19255446045143 18393484233509 -4251490219988 15024709618745 -6265764232502 -10565233317818 3772903365601 -9818067060798 -16415763429312 -15128974796983 2275660459409 3297900503632 16182058464702 7219597158423 -7370341301...
output:
86523
result:
ok single line: '86523'
Test #16:
score: 0
Accepted
time: 96ms
memory: 6328kb
input:
400 762 330 158 514 666 258 152 512 342 310 622 476 760 224 92 480 134 98 128 474 578 792 528 274 364 256 424 444 596 418 198 516 404 736 756 664 366 86 794 414 524 748 660 602 200 396 652 398 368 12 332 738 106 34 508 168 136 170 458 620 644 234 482 742 138 236 548 56 772 18 36 522 504 636 150 570 ...
output:
10706600
result:
ok single line: '10706600'
Test #17:
score: 0
Accepted
time: 107ms
memory: 7676kb
input:
400 3739 141 610 1971 120 1939 1421 1820 381 2029 1509 3480 2860 491 1331 2170 3279 1571 2700 371 1170 439 1810 60 3601 2440 2191 1960 3391 3131 2770 2880 1721 779 3809 1379 450 3259 2819 831 820 1619 2669 2280 3250 659 2380 1011 3451 3721 3269 2101 191 2890 2201 2640 669 760 2650 1861 2071 101 3330...
output:
53691575
result:
ok single line: '53691575'
Test #18:
score: 0
Accepted
time: 103ms
memory: 7420kb
input:
400 4137 7519 5259 2062 5059 57 3821 6399 6838 1143 6997 3641 7917 7660 5338 2019 3701 2597 7043 222 3897 4842 3621 4298 4943 6118 2262 4342 439 2920 860 1740 301 7562 3240 1282 7277 1822 4640 2681 2961 759 3501 6359 5579 5901 5000 3799 3577 1778 7600 3399 7458 2721 6143 4718 2280 2518 6761 2480 139...
output:
107404560
result:
ok single line: '107404560'
Test #19:
score: 0
Accepted
time: 106ms
memory: 7928kb
input:
400 6934 1501 9604 148 5275 10294 10862 9693 4225 7765 116 3866 3543 4647 416 11102 2883 2579 8276 1110 2490 4260 8970 7682 8216 10377 6181 11246 10352 6511 4080 269 4737 11309 5489 10829 4947 1649 11580 3065 8102 9715 4619 1560 9056 386 7113 2284 9659 10263 8883 5847 11399 6421 4498 5523 3959 9149 ...
output:
161180629
result:
ok single line: '161180629'
Test #20:
score: 0
Accepted
time: 106ms
memory: 6680kb
input:
400 9044 10507 2803 45 2492 15457 8651 15049 2295 15208 15345 5148 17344 893 19646 11157 4457 7804 16351 2654 18756 7244 18845 4647 1795 11552 9000 450 9743 16905 8508 11707 5703 8255 17255 18456 4604 2448 14155 4347 12849 15899 4995 7199 13199 9704 12994 9442 1104 17796 9501 1354 1892 7892 7652 235...
output:
268564861
result:
ok single line: '268564861'
Test #21:
score: 0
Accepted
time: 106ms
memory: 7716kb
input:
400 134908533454450647 352658606865045145 581684580480093663 497943896187183853 408592795441246050 395165072031649730 146254574430314591 202420064750042310 647642414828915568 601692522952567225 423659429164712656 367352668332523510 16659330113319985 441267266242106592 311084665089366232 308060910038...
output:
404142621
result:
ok single line: '404142621'
Test #22:
score: 0
Accepted
time: 102ms
memory: 6964kb
input:
400 226327251007519290 238750958880838382 425329173403150033 1093881274700431 339265739779043165 418997765106739507 137049815148662314 192757708234547476 135573729210765909 349074451774710340 232391953665474341 266133395498262705 40154598874154329 52014984967455962 331772659893477984 375171531568920...
output:
260934791
result:
ok single line: '260934791'
Test #23:
score: 0
Accepted
time: 106ms
memory: 7136kb
input:
400 269524014049478356 444893904523880884 291696049236349346 247695998750836823 125437811570950709 138324386893112476 632621925085650469 249862747655808151 198789353795262887 197170655685049192 667318156395540426 685887272939973145 479169603920672621 1447043625030237 401490255666325100 3553147393987...
output:
398852089
result:
ok single line: '398852089'
Test #24:
score: 0
Accepted
time: 107ms
memory: 5932kb
input:
400 206684761968587004 540753612188738013 518941982997340809 155408859082188799 509314456610970596 396461325608634748 5808141544800415 516256528119624178 490966425894710583 307806136732640691 174457477712985204 487114098343416438 477055664306066397 27417294768408065 99536586579458612 337033495796696...
output:
284771229
result:
ok single line: '284771229'
Test #25:
score: 0
Accepted
time: 107ms
memory: 7084kb
input:
400 104709922716918275 200659283692875243 234937120796530004 242306130302808787 75683413162551920 92358879309416622 175479935967300382 144320662499313280 141273892653381114 221438699128458677 3631988225540120 293594775120064264 49767688835720269 294632926566924237 126512738496852428 5942375449496023...
output:
411830112
result:
ok single line: '411830112'
Test #26:
score: 0
Accepted
time: 106ms
memory: 7364kb
input:
400 92112158220316422 49665142814083708 18170105895376349 108360361739698886 4365890956761700 5763708133590982 116056757945831490 6983650619010597 50101454843985705 90569351596714450 19272788199756617 65383276276166131 15349493935270706 25467088058513170 36579129693119796 28857137753738956 384163452...
output:
276063785
result:
ok single line: '276063785'
Test #27:
score: 0
Accepted
time: 102ms
memory: 5748kb
input:
400 151693657797317689 247303542798523041 354026862284893685 119534592202446766 251881275437319062 198412375553541731 157413417377042579 213423403126001231 320079167383081959 176752932831743247 335831974200298748 230953010812564270 311900087127196189 263712358349546621 74578477762242816 194984859907...
output:
418813298
result:
ok single line: '418813298'
Test #28:
score: 0
Accepted
time: 104ms
memory: 7260kb
input:
400 128512199698756100 27912001283788196 80181450926331334 143494922359039871 39511499528321639 66736940175768819 155466685031663304 47911518663586299 92163968651847354 162610302706223431 15964993559078544 79562210660835744 95688234307092165 31765430895040143 99986099679113859 124477024770866140 119...
output:
280942132
result:
ok single line: '280942132'
Test #29:
score: 0
Accepted
time: 106ms
memory: 6660kb
input:
400 443014561711115221 316261990970519437 575808081706200325 252418763234976819 298058305788459084 5078827543966376 584636713513502662 448544809608633151 526305296019350622 402558484549552237 163641060879711804 301377251573862491 642358257511892988 421259595404205797 257963572003669108 9956330277516...
output:
421870764
result:
ok single line: '421870764'
Test #30:
score: 0
Accepted
time: 109ms
memory: 6904kb
input:
400 458973924927752908 209187314123266600 544053115329760003 353654080640321655 372978171514507153 144670872849428885 453061166044955211 555746229788300063 174067529767534132 12387989902756644 55988050558053191 272072946746595701 294300685228959522 391206568293033918 535620872917883480 2556141955276...
output:
268798890
result:
ok single line: '268798890'
Test #31:
score: 0
Accepted
time: 36ms
memory: 7356kb
input:
400 -8 -8 4 10 -5 -9 5 -4 0 6 -8 3 1 -3 3 4 -1 -4 10 -4 4 -6 1 -2 8 0 -1 -3 -8 5 8 5 -6 -7 -6 -2 -8 -9 -5 -5 -10 4 8 -1 8 0 6 -9 5 -2 -4 3 10 0 5 -1 -1 6 9 -8 -10 -7 -7 -5 10 -6 -1 -3 -7 6 -8 7 7 1 -8 9 0 -9 6 -3 10 -4 -4 3 -9 -2 1 1 -6 -5 10 -9 -9 -3 -10 2 10 -1 -9 -9 4 2 -9 -1 2 -10 -8 -3 -8 3 6 -...
output:
98289
result:
ok single line: '98289'
Test #32:
score: 0
Accepted
time: 49ms
memory: 6764kb
input:
400 -88 84 46 57 89 -95 94 -18 82 -28 -17 95 82 34 -96 40 -93 16 50 -89 -23 -13 71 23 -19 88 66 81 -15 -82 -72 -76 -83 98 -21 -65 56 0 -83 65 -59 18 16 63 4 54 46 -56 -15 -69 -31 -74 18 -85 86 -60 -15 50 -33 -38 -41 -96 76 5 70 -56 74 -84 -5 47 33 95 -31 -99 -58 -87 -18 33 -13 83 90 22 6 -86 -22 82 ...
output:
93903
result:
ok single line: '93903'
Test #33:
score: 0
Accepted
time: 55ms
memory: 6080kb
input:
400 -68 30 -52 -20 2 -98 -79 -29 -40 -46 -23 -100 72 -8 -1 26 -68 62 80 -73 -5 -53 -47 87 82 38 71 -59 -84 -90 -39 91 34 -70 -98 -89 -52 9 -64 -65 -31 -39 61 -17 -45 78 47 -92 -23 28 54 -97 -98 -83 -26 34 22 -25 -52 39 -52 37 51 -37 74 -85 93 -5 15 -86 -98 -58 77 8 95 45 10 -71 92 63 67 64 -69 -17 -...
output:
483202
result:
ok single line: '483202'
Test #34:
score: 0
Accepted
time: 59ms
memory: 7412kb
input:
400 -65 92 -54 -18 -100 -20 27 75 -43 -24 -3 42 58 20 -85 -5 -10 47 -48 31 -83 85 3 -36 -50 -64 23 -92 32 -74 95 -14 98 -55 -6 -69 -29 -25 25 12 62 -30 11 30 76 -38 -87 -63 51 -59 92 56 -47 -97 21 -9 81 -68 -65 14 -5 57 -86 49 -66 85 7 28 -64 21 -12 -37 -31 59 86 6 85 4 41 57 39 -55 79 99 -87 -39 -2...
output:
4442745
result:
ok single line: '4442745'
Test #35:
score: 0
Accepted
time: 65ms
memory: 6780kb
input:
400 457 871 536 865 -875 0 -239 20 551 -154 -913 699 -518 243 529 -459 -318 790 81 -731 891 212 -829 -402 -837 316 173 -482 -701 591 -972 -2 -449 -587 -439 116 -623 -250 985 440 -138 81 847 964 494 -37 257 805 637 -880 -984 -760 1 -313 16 -713 375 -772 -542 431 -558 951 -998 -408 -79 761 -475 -142 3...
output:
4811765
result:
ok single line: '4811765'
Test #36:
score: 0
Accepted
time: 69ms
memory: 7944kb
input:
400 -619 528 -95 129 639 -614 -820 -11 137 -324 -651 -77 -326 -399 -648 -45 80 456 -159 -926 275 458 373 788 33 895 -103 184 444 619 358 621 46 -830 412 370 787 489 128 -548 37 520 -628 -336 -558 -592 134 -443 -564 936 946 439 -288 178 512 -504 -522 804 -741 168 -199 542 -964 -953 868 404 603 152 -4...
output:
46930589
result:
ok single line: '46930589'
Test #37:
score: 0
Accepted
time: 75ms
memory: 6192kb
input:
400 4908 5151 -1184 6036 331 -9643 -9524 9651 -4025 1669 8246 143 -322 139 3244 -7864 3502 5006 3409 9835 5153 8989 8029 6881 5268 1372 1106 -8926 5750 -7988 -8309 -5087 -5262 5695 1010 1572 -4840 -2007 8177 -3174 -4222 593 720 5056 -6199 -5795 -9922 -7212 1133 26 1735 -8262 9742 -6677 -5233 -4766 -...
output:
48885631
result:
ok single line: '48885631'
Test #38:
score: 0
Accepted
time: 69ms
memory: 6196kb
input:
400 6766 -8491 -1834 4397 -4459 6058 2170 4062 3098 -2859 -3423 4209 3221 732 -5745 4789 -7288 -5280 1539 -4692 3574 626 -3994 -8967 6994 4254 -9936 -4324 -114 -9910 -9897 6650 -1397 -9405 3188 -9323 -1965 -5994 -2899 3232 -1579 -1 6764 7420 -7438 3644 2023 -6690 -3432 8328 5142 -6195 6721 -3192 182...
output:
455991027
result:
ok single line: '455991027'
Test #39:
score: 0
Accepted
time: 77ms
memory: 6196kb
input:
400 10634 -49702 22753 32169 96639 72942 18751 -84477 -84100 -78344 37714 -79287 18380 -29959 -66480 -2463 11630 -53788 30324 -68564 -77819 -74145 74135 11241 7617 95565 -17754 -60358 10754 44756 -37941 6668 -52920 -57924 31775 -76918 98823 17591 -85419 -96871 83028 -2167 -47607 88216 -70646 -25287 ...
output:
496344141
result:
ok single line: '496344141'
Test #40:
score: 0
Accepted
time: 75ms
memory: 6976kb
input:
400 -283741211542377111 195211939001438272 -54976661003728034 -570950679244615514 199018540813358830 -241680026886657745 930666691610703859 -265584365923219645 309125067371032372 860356881916052483 -758143963222015076 214032920491472127 -657526444478068815 517732222329923743 82029985806724852 896875...
output:
499117359
result:
ok single line: '499117359'