QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#200805 | #5123. Streets | 275307894a | TL | 1999ms | 12648kb | C++14 | 3.1kb | 2023-10-04 20:26:28 | 2023-10-04 20:26:28 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;using LL=__int128;
const int N=1e5+5,M=2.1e4+5,K=600+5,mod=1e9+7,Mod=mod-1;const db eps=1e-6;const int INF=1e9+7;mt19937 rnd(263082);
int n,m,T,A[N],B[N],f[N];
pii X[N],Y[N];int Xh,Yh;
int fa[N];
int GF(int x){return fa[x]^x?fa[x]=GF(fa[x]):x;}
vector<int> S[N];int pre[N];
ll C;
ll dd(ll x,ll y){return (x+y-1)/y;}
void Add(int x,int ti){
int y=GF(x-1);if(!y) return;
if(1ll*X[x].se*X[y].fi>=1ll*X[y].se*X[x].fi) return;
ll w=dd(C*X[x].fi-C*X[y].fi,1ll*X[y].se*X[x].fi-1ll*X[x].se*X[y].fi);
if(w>Y[Yh].fi) return;
/*if((C-1ll*w*X[x].se)*1.0/X[x].fi+eps<(C-1ll*w*X[y].se)*1.0/X[y].fi){
cerr<<w<<'\n';
cerr<<X[x].se<<' '<<X[x].fi<<' '<<X[y].se<<' '<<X[y].fi<<' '<<C<<'\n';
printf("%.10lf %.10lf\n",(C-1ll*w*X[x].se)*1.0/X[x].fi,(C-1ll*w*X[y].se)*1.0/X[y].fi);
}
assert((C-1ll*w*X[x].se)*X[y].fi>=(C-1ll*w*X[y].se)*X[x].fi);*/
S[pre[w]].emplace_back(x);assert(pre[w]>=ti);
}
void Solve(){
int i,j;scanf("%d%d%d",&n,&m,&T);
for(i=1;i<=n;i++) scanf("%d",&A[i]);for(i=1;i<=n;i++) scanf("%d",&B[i]);
Me(f,0x3f);for(i=1;i<=n;i++) for(j=i;j<=n;j++) f[A[j]-A[i]]=min(f[A[j]-A[i]],B[i]+B[j]);
for(i=1;i<=1e5;i++) if(f[i]<=1e8) X[++Xh]=make_pair(i,f[i]);
for(i=1;i<=m;i++) scanf("%d",&A[i]);for(i=1;i<=m;i++) scanf("%d",&B[i]);
Me(f,0x3f);for(i=1;i<=m;i++) for(j=i;j<=m;j++) f[A[j]-A[i]]=min(f[A[j]-A[i]],B[i]+B[j]);
for(i=1;i<=1e5;i++) if(f[i]<=1e8) Y[++Yh]=make_pair(i,f[i]);
cerr<<Xh<<' '<<Yh<<'\n';
for(i=1;i<=Yh;i++) fill(pre+Y[i-1].fi+1,pre+Y[i].fi+1,i);
while(T--){
scanf("%lld",&C);ll ans=0;
iota(fa+1,fa+Xh+1,1);for(i=1;i<=Yh;i++) S[i].clear();
for(i=2;i<=Xh;i++) Add(i,0);
for(i=1;i<=Yh;i++) {
for(int j=0;j<S[i].size();j++){
int p=S[i][j];if(fa[p]^p) continue;
int y=GF(p-1);if(!y) continue;
if((C-1ll*Y[i].fi*X[y].se)*X[p].fi>(C-1ll*Y[i].fi*X[p].se)*X[y].fi) continue;
fa[y]=y-1;Add(p,i);
}
int l=0,r=Xh+1,mid;
db p=-1e18;
/*int x=GF(Xh);while(x){
if((C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi+1<p){
printf("%lf %lf\n",(C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi+eps,p);
}
//assert((C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi+1>=p);
p=(C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi;//printf("%.9lf ",p);
if((C-1ll*Y[i].fi*X[x].se)*1.0/X[x].fi>=Y[i].se) ans=max(ans,1ll*Y[i].fi*X[x].fi);
x=GF(x-1);
}*/
while(l+1<r) mid=l+r>>1,(!GF(mid)||C-1ll*Y[i].fi*X[GF(mid)].se>=1ll*X[GF(mid)].fi*Y[i].se?l:r)=mid;
if(GF(l)) ans=max(ans,1ll*Y[i].fi*X[GF(l)].fi)/*,cerr<<Y[i].fi<<' '<<X[GF(l)].fi<<'\n'*/;
}
printf("%lld\n",ans);
// if(T==80) exit(0);
}
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 8688kb
input:
3 4 20 1 3 4 3 1 2 1 3 4 7 4 2 1 2 1 5 6 7 9 10 11 12 15 16 17 22 23 28 30 35 43 47 49 57
output:
0 0 1 1 1 2 2 3 3 4 4 6 6 9 9 12 12 12 18 18
result:
ok 20 numbers
Test #2:
score: 0
Accepted
time: 1966ms
memory: 12052kb
input:
4995 4998 100 4 7 20 34 44 100 102 130 175 198 205 250 257 259 267 278 300 324 337 346 353 364 403 427 439 440 451 523 532 534 555 599 634 639 756 802 805 825 855 859 890 905 912 915 953 989 1014 1031 1052 1059 1097 1124 1183 1216 1297 1308 1337 1342 1361 1392 1400 1421 1451 1471 1523 1537 1542 1619...
output:
9991201920 9941157660 8387550150 9892186440 9803600290 9986903784 9928424616 9892186440 9831470090 9768930402 9831470090 9058876564 9803600290 9857548260 9944740920 9892186440 9885418060 9831470090 9857548260 9768930402 8671693002 9803600290 9911595765 9058876564 9803600290 9838238470 9024072106 980...
result:
ok 100 numbers
Test #3:
score: 0
Accepted
time: 1999ms
memory: 12648kb
input:
4995 4996 100 72 80 119 144 216 272 283 292 300 313 317 332 337 338 369 374 416 422 447 480 506 535 571 581 590 592 604 614 622 639 676 677 691 695 700 723 739 742 748 755 779 787 797 839 847 856 864 878 886 888 890 894 898 899 904 1007 1023 1049 1051 1061 1070 1122 1125 1153 1168 1187 1190 1225 124...
output:
9985005184 9855576720 9855576720 6122924640 9437544131 9627630660 9951648960 9627630660 9635613716 9855576720 9855576720 9627630660 9936899280 9960518700 9254863411 9855576720 9936899280 9974416128 9941882280 7314670570 9984905280 9254274235 9818294436 9855576720 9945769020 9985005184 9855576720 981...
result:
ok 100 numbers
Test #4:
score: 0
Accepted
time: 1939ms
memory: 12300kb
input:
4999 4998 100 24 28 58 91 107 122 129 134 137 166 200 216 248 266 329 336 362 389 392 399 404 419 547 557 564 573 642 680 682 720 727 728 824 826 853 861 865 897 901 902 908 911 932 953 956 962 977 982 997 1002 1022 1025 1035 1062 1068 1085 1120 1168 1172 1192 1198 1205 1274 1294 1371 1372 1373 1410...
output:
9991701692 9253373820 9755390874 9968222577 9377310990 9829353624 9804851874 8890538665 9949256772 9253373820 9110273475 9377310990 8890538665 9794940174 9962335026 9444281184 9514977448 9708304002 9110273475 9377310990 8890538665 9253373820 9175336560 9664890422 6123991927 9621153720 9377310990 988...
result:
ok 100 numbers
Test #5:
score: 0
Accepted
time: 1963ms
memory: 11844kb
input:
4995 4999 100 15 43 47 59 95 107 176 180 264 328 338 362 367 369 373 391 428 484 502 550 573 577 596 614 621 628 649 676 678 702 705 715 748 755 764 779 800 805 842 846 854 858 888 909 928 946 998 1018 1036 1082 1084 1087 1093 1102 1113 1120 1128 1137 1160 1164 1173 1200 1241 1251 1260 1269 1298 130...
output:
9990601368 9839407611 9955914580 9634428612 9910930780 9843029676 9790830072 9790830072 9821886558 9921626928 7879145340 9944418720 9929496720 9987203312 9895336396 9880488046 9843029676 9821886558 9928824336 7899488010 9821886558 9910930780 9821886558 9988802736 9854913855 9929496720 9889812895 966...
result:
ok 100 numbers
Test #6:
score: 0
Accepted
time: 1946ms
memory: 12420kb
input:
4997 4999 100 45 46 51 93 99 135 140 144 186 189 206 229 231 232 246 251 267 275 297 364 395 466 474 486 489 504 558 559 571 591 599 623 632 645 646 732 740 749 753 780 781 870 904 920 954 956 971 983 984 1010 1022 1040 1045 1085 1108 1122 1129 1164 1210 1215 1243 1245 1262 1307 1317 1371 1425 1472 ...
output:
9989602700 8899349230 9798172153 9798172153 9905126028 9481804741 9798172153 9687737143 9595807459 9905126028 9671520110 9905126028 9798172153 9809016672 9706242469 9900946356 9938085284 9798172153 9798172153 1563896 8998119272 8899349230 9798172153 9942765826 9595807459 9931099704 9931099704 990512...
result:
ok 100 numbers
Test #7:
score: -100
Time Limit Exceeded
input:
4998 4999 100 15 16 27 35 48 49 58 69 104 110 137 187 203 219 306 338 349 362 382 429 465 475 477 548 549 586 631 674 691 712 730 794 813 831 859 874 953 975 981 988 994 1027 1034 1048 1075 1084 1106 1108 1127 1134 1138 1140 1194 1223 1231 1237 1243 1252 1312 1337 1340 1343 1351 1359 1373 1419 1444 ...
output:
9987202871 322360992 34221228 170018460 2077200000 367788248 1849331484 104562900 130121250 667780755 14502428 199090845 70810920 229443360 34962225 732300000 593392380 465415095 179545680 11473369 765100000 952200000 10389199 489931907 1478004636 95030900 377990696 144950880 621853944 400045988 820...