QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #108646 | #5123. Streets | shenxinge | TL | 3ms | 4112kb | C++14 | 987b | 2023-05-25 21:42:24 | 2023-05-25 21:42:25 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int maxn(1e5+10);
int n,m,T,X[maxn],Y[maxn],A[maxn],B[maxn],va[maxn],vb[maxn];
vector<int> vecx,vecy;
#define all(x) x.begin(),x.end()
signed main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
cin >> n >> m >> T;memset(va,0x3f,sizeof va),memset(vb,0x3f,sizeof vb);
for(int i=1;i<=n;i++) cin >> X[i];for(int i=1;i<=n;i++) cin >> A[i];
for(int i=1;i<=m;i++) cin >> Y[i];for(int i=1;i<=m;i++) cin >> B[i];
for(int i=1;i<=n;i++) for(int j=1;j<i;j++) va[X[i]-X[j]]=min(va[X[i]-X[j]],A[i]+A[j]),vecx.push_back(X[i]-X[j]);
for(int i=1;i<=m;i++) for(int j=1;j<i;j++) vb[Y[i]-Y[j]]=min(vb[Y[i]-Y[j]],B[i]+B[j]),vecy.push_back(Y[i]-Y[j]);
sort(all(vecx)),vecx.resize(unique(all(vecx))-vecx.begin());
sort(all(vecy)),vecy.resize(unique(all(vecy))-vecy.begin());
for(int c;T--;){int ans=0;
cin >> c;for(int x:vecx) for(int y:vecy) if(x*vb[y]+y*va[x]<=c) ans=max(ans,x*y);
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 4112kb
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: -100
Time Limit Exceeded
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...