QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#85903 | #5453. Mana Collection | Appleblue17 | 8.333333 | 0ms | 3644kb | C++14 | 2.6kb | 2023-03-08 21:02:15 | 2023-03-08 21:02:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const long long N=22,M=3e5+5,INF=1e18;
long long n,m,q;
long long a[N],G[N][N];
long long K[M],dp[M][N];
long long X[N],U[N];
long long v[N],vid;
class segtree{
public:
struct seg{
long long k,b;
}P[M];
long long id;
double cal(long long pos,long long x){
return v[pos]*P[x].k+P[x].b;
}
long long f[M*4];
void modify(long long l,long long r,long long o,long long L,long long R,long long x){
long long mid=(l+r)>>1;
if(L<=l && r<=R){
if(l==r){
if(cal(l,x)>cal(l,f[o])) f[o]=x;
return ;
}
if(cal(mid,x)>cal(mid,f[o])) swap(f[o],x);
if(cal(l,x)>cal(l,f[o])) modify(l,mid,o<<1,L,R,x);
else if(cal(r,x)>cal(r,f[o])) modify(mid+1,r,o<<1|1,L,R,x);
return ;
}
if(L<=mid) modify(l,mid,o<<1,L,R,x);
if(R>mid) modify(mid+1,r,o<<1|1,L,R,x);
}
long long query(long long l,long long r,long long o,long long pos){
if(l==r) return cal(pos,f[o]);
long long mid=(l+r)>>1;
long long tot=cal(pos,f[o]);
if(pos<=mid) tot=max(tot,query(l,mid,o<<1,pos));
else tot=max(tot,query(mid+1,r,o<<1|1,pos));
return tot;
}
}F[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
for(long long i=0;i<n;i++) cin>>a[i];
for(long long i=0;i<n;i++)
for(long long j=0;j<n;j++)
if(i!=j) G[i][j]=INF;
for(long long i=1;i<=m;i++){
long long u,v,w; cin>>u>>v>>w; u--,v--;
G[u][v]=w;
}
for(long long k=0;k<n;k++)
for(long long i=0;i<n;i++)
for(long long j=0;j<n;j++)
G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
for(long long mac=0;mac<(1<<n);mac++){
for(long long i=0;i<n;i++)
if(mac>>i & 1) K[mac]+=a[i];
}
for(long long mac=0;mac<(1<<n);mac++)
for(long long i=0;i<n;i++)
dp[mac][i]=INF;
for(long long i=0;i<n;i++) dp[1<<i][i]=0;
for(long long mac=0;mac<(1<<n);mac++){
for(long long i=0;i<n;i++){
if(!(mac>>i & 1) || dp[mac][i]==INF) continue;
for(long long j=0;j<n;j++){
if((mac>>j & 1) || G[i][j]==INF) continue;
long long nmac=mac | (1<<j);
dp[nmac][j]=min(dp[nmac][j],dp[mac][i]+G[i][j]*K[mac]);
}
}
}
cin>>q;
for(long long i=1;i<=q;i++){
cin>>X[i]>>U[i]; U[i]--;
v[i]=X[i];
}
sort(v+1,v+q+1);
vid=unique(v+1,v+q+1)-v-1;
for(long long i=1;i<=q;i++)
X[i]=lower_bound(v+1,v+vid+1,X[i])-v;
for(long long i=0;i<n;i++){
for(long long mac=0;mac<(1<<n);mac++){
if(dp[mac][i]<INF){
F[i].P[++F[i].id]={K[mac],-dp[mac][i]};
F[i].modify(1,vid,1,1,vid,F[i].id);
}
}
}
for(long long i=1;i<=q;i++){
long long x=X[i],u=U[i];
long long ans=F[u].query(1,vid,1,x);
cout<<ans<<'\n';
}
}
詳細信息
Test #1:
score: 4.16667
Accepted
time: 0ms
memory: 3432kb
input:
2 1 1 10 1 2 10 4 5 1 5 2 100 1 100 2
output:
5 50 100 1090
result:
ok 4 number(s): "5 50 100 1090"
Test #2:
score: 4.16667
Accepted
time: 0ms
memory: 3644kb
input:
4 8 50000000 100000000 20000000 70000000 1 2 20 2 1 50 2 3 90 1 3 40 3 1 10 4 1 25 1 4 5 4 3 70 3 8 3 1000000000 1 500000 4
output:
160000000 239999988050000000 119992550000000
result:
ok 3 number(s): "160000000 239999988050000000 119992550000000"
Test #3:
score: 0
Runtime Error
input:
10 90 95677166 99413032 90081107 97391055 96848266 92520734 90623124 96509760 95451402 99152599 1 10 94105173 3 9 91922842 5 2 90862613 8 3 94419460 4 7 90084016 6 4 90693719 10 8 97125103 2 1 93286961 5 10 91546334 4 8 92053784 8 5 96537357 3 1 95913083 1 3 95054163 2 8 95986698 7 6 95233705 8 10 9...
output:
result:
Test #4:
score: 0
Runtime Error
input:
10 90 48104151 45958764 10384927 58976477 4508220 48401738 63414134 56241331 43456656 5364282 4 3 34321182 3 8 6111111 10 3 89336838 7 6 15869517 9 6 45416322 6 8 65416493 8 7 68165563 1 10 17098910 5 7 23144280 10 5 41059929 4 5 83655589 8 2 11141593 10 4 47789741 6 4 15702833 6 5 3119771 9 5 79973...
output:
result:
Test #5:
score: 0
Runtime Error
input:
10 87 61275784 16282886 58999609 52155395 53012427 89533414 15431931 35150033 58505854 59445220 9 5 3496028 7 6 17372183 8 1 287847 2 7 19991219 4 5 40820118 4 9 38405375 1 4 52061958 1 3 95765844 9 7 88432897 10 3 62181295 2 4 2070594 6 8 38490628 5 1 74834920 5 2 58054124 5 10 53052912 9 10 799932...
output:
result:
Test #6:
score: 0
Runtime Error
input:
10 90 95356560 91592390 93197917 98740065 97680300 92412698 94329246 97243226 90272368 97469569 10 6 99745186 9 3 93877572 4 3 95758698 6 10 91855996 5 1 90121278 5 4 95076290 8 2 99231614 10 3 93399573 4 1 91994993 6 5 94052740 5 2 96068955 2 10 91338395 7 10 91890588 4 7 94880828 1 6 96554961 7 5 ...
output:
result:
Test #7:
score: 0
Runtime Error
input:
10 89 93795458 90122950 90809309 91512557 99759510 98879743 90406791 91988172 98723686 97265654 3 1 92410620 6 10 787488884 1 7 872243221 5 10 93057933 8 3 90945371 7 4 94869387 1 4 90377187 9 1 92060643 10 8 98532700 9 5 97326866 10 2 98947943 1 6 96415500 10 4 92676865 8 7 92985312 9 6 98444476 1 ...
output:
result:
Test #8:
score: 0
Runtime Error
input:
10 89 1382293 67193843 93859961 477481 92652257 99885499 50256117 70192761 34119368 16710544 9 10 42167550 5 8 37587488 6 1 39681485 2 6 83885591 2 8 63502599 2 7 96584704 3 2 28849619 1 2 89615158 7 6 49082361 6 7 6114228 6 10 45456432 7 4 87603741 1 8 8377024 5 9 3400067 10 4 42824742 8 1 34659500...
output:
result:
Test #9:
score: 0
Runtime Error
input:
10 90 97766575 91352441 94775266 90513638 95828190 90356289 90495007 98680228 93010243 98543991 1 3 99109059 5 8 90074960 6 5 90055463 6 1 90819495 8 9 98346448 8 5 90223065 10 9 92780029 3 6 90250424 9 1 96050114 7 3 90956675 4 2 92037130 4 7 90691071 2 3 91565269 8 3 94131990 2 9 97006947 4 10 942...
output:
result:
Test #10:
score: 0
Runtime Error
input:
18 306 97592575 5845225 97094410 61652068 60514373 77053365 82408570 65859870 52309184 11075991 79663473 60429988 64440299 88087418 51883591 39638284 31941363 95790465 18 7 12121248 13 6 28252098 14 12 2481192 4 16 54868108 13 15 33001477 7 13 15911113 8 16 47075458 7 14 51352052 9 2 41100503 18 10 ...
output:
result:
Test #11:
score: 0
Runtime Error
input:
18 306 54786856 23623482 37443275 34976477 27052191 21997277 93803298 62986079 72289998 36640646 66962609 75940630 20835955 36012773 32492294 69398349 49378951 13097897 7 10 5470000 8 7 53513890 3 15 38460382 7 16 19142503 5 14 45517218 18 17 42648313 8 18 48305235 4 16 41424027 5 12 52928903 5 4 44...
output:
result:
Test #12:
score: 0
Runtime Error
input:
18 303 87437585 22204459 77335222 63373455 24384957 40111770 61538701 65736765 65450807 20008686 60461910 77184085 62951808 75441264 35010255 67513271 41855413 84760939 6 14 45984925 3 6 5610402 8 1 49203830 8 3 53792394 10 8 11629718 1 12 20708032 4 6 14035635 15 18 487975772 3 1 28292662 3 10 2399...
output:
result:
Test #13:
score: 0
Runtime Error
input:
18 300 95399651 98514702 95906995 99120696 97373712 99841892 95487998 98629037 97207398 99163728 97816361 94919203 95202846 96133518 98849047 99498436 94447669 96164861 10 8 54922237 1 2 55368382 10 4 54029624 9 8 55267410 14 2 53427574 14 18 54579322 3 9 54230956 2 9 52630731 4 16 53837522 3 7 8372...
output:
result:
Test #14:
score: 0
Runtime Error
input:
18 306 94983318 99500146 99056770 99199070 96785433 94689368 96603811 97464542 96757856 95575432 97758260 96271537 94822391 98897205 96531324 95046283 95759027 99689250 14 18 54518764 3 8 54402270 16 8 52601874 3 11 52679529 13 6 54902169 1 10 54363631 4 2 55268135 5 6 52963284 16 1 52494958 12 11 5...
output:
result:
Test #15:
score: 0
Runtime Error
input:
16 240 47666600 44327219 49953274 41785108 32073587 24424080 30939819 78762914 90224099 59998405 64133109 48652631 22221281 96356764 38490560 116991 1 2 91993819 1 3 97619874 1 4 89451708 1 5 79740187 1 6 94041352 1 7 78606419 1 8 126429514 1 9 137890699 1 10 107665005 1 11 111799709 1 12 96319231 1...
output:
result:
Test #16:
score: 0
Runtime Error
input:
16 240 42361838 31647618 32114308 8782634 17345648 68132951 88405030 26942819 62741100 66985295 20876520 8437021 27114112 66925976 7183979 94977427 2 15 58174648 8 15 34276605 6 10 58212397 2 13 58804593 13 9 54225029 15 14 33719184 11 13 61087050 9 10 28955627 6 2 10289499 10 2 20518981 13 8 837959...
output:
result:
Test #17:
score: 0
Runtime Error
input:
16 240 94916675 95328982 94461789 98179130 96410042 95984504 99026406 96722757 98043813 97126519 99521857 99735210 99833885 94048501 93989630 97045699 5 6 61339353 7 11 61447467 16 7 59391553 15 5 61958471 13 2 59603541 13 16 60250166 2 3 61615858 16 3 60312774 14 6 61619256 9 2 61767236 7 12 608785...
output:
result:
Test #18:
score: 0
Runtime Error
input:
17 269 10989016 28905152 56011456 36383994 32588074 40160206 81943847 29653018 81874689 11531228 28812650 79088847 31042740 89163087 58731031 57356809 5076315 2 4 54972232 1 17 48426734 17 8 7126979 7 2 16376090 10 7 30672058 8 17 55225752 2 6 312152706 4 12 1609956 11 10 44726737 7 6 16333848 17 9 ...
output:
result:
Test #19:
score: 0
Runtime Error
input:
17 241 20878633 21727433 30788417 1919362 24415556 26527489 14285320 3437901 23517959 28616698 11361867 15220890 21496568 20470194 31073215 5981317 11566475 1 2 42606066 1 3 98682648 1 4 22797995 1 5 45294189 1 6 47406122 1 7 35163953 1 8 24316534 1 9 44396592 1 10 49495331 1 11 32240500 1 12 360995...
output:
result:
Test #20:
score: 0
Runtime Error
input:
17 241 26896510 11416857 23632920 22663714 10426416 1449988 6534437 21431904 6332558 5350871 7478640 7144884 1667707 31989074 24328111 14606283 16379885 1 2 38313367 1 3 50529430 1 4 89019020 1 5 37322926 1 6 28346498 1 7 33430947 1 8 48328414 1 9 33229068 1 10 32247381 1 11 48235649 1 12 34041394 1...
output:
result:
Test #21:
score: 0
Runtime Error
input:
18 273 5856998 26869251 1761061 23339731 6696975 12073312 26103914 9146585 14284107 2290011 33149581 6690606 1938529 2611081 4180578 15507572 12766646 8196720 1 2 32726249 1 3 7618059 1 4 29196729 1 5 12553973 1 6 17930310 1 7 31960912 1 8 15003583 1 9 20141105 1 10 8147009 1 12 12547604 1 13 779552...
output:
result:
Test #22:
score: 0
Runtime Error
input:
18 273 18655021 10530209 4072104 27397860 1799797 31844906 10224838 22363503 8387103 25160565 867464 18587455 28492008 3583506 7250222 12947265 13542506 15353338 1 2 29185230 1 3 22727125 1 4 46052881 1 5 20454818 1 6 50499927 1 8 41018524 1 9 44747129 1 10 43815586 1 11 28438355 1 12 37242476 1 13 ...
output:
result:
Test #23:
score: 0
Runtime Error
input:
18 273 18425031 23650394 24880771 20922906 26575943 17784399 1257646 4304768 2028569 32225860 3162758 23575563 21688821 6218252 30502483 720206 33244851 27314277 1 2 43683269 1 3 61643789 1 4 75113213 1 5 58792271 1 6 52052510 1 7 28904939 1 8 22817172 1 9 26122275 1 11 24226530 1 12 77523542 1 13 6...
output:
result:
Test #24:
score: 0
Runtime Error
input:
18 273 26613501 27441209 12794702 13658897 32546072 2607103 21792275 12508707 8092259 2836952 26658654 15275240 16574454 31623641 1150608 21764569 30050392 12599166 1 2 54054710 1 3 39408203 1 4 40272398 1 5 59159573 1 6 29220604 1 7 48405776 1 9 34705760 1 10 29450453 1 11 53272155 1 12 41888741 1 ...