QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694989 | #7078. Tower of the Sorcerer | ucup-team4352# | WA | 20ms | 15112kb | C++23 | 1.7kb | 2024-10-31 19:05:33 | 2024-10-31 19:05:34 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define lowbit(x) (x&-x)
#define log(x) (31^__builtin_clz(x))
using namespace std;
const int maxn=1e5+5;
ll hp[maxn];
ll h[maxn],at[maxn];
ll dis[maxn];
struct node{
int v;
ll w;
};
vector<node>e[maxn];
void solve(){
ll n,t,mx=0;
cin>>n>>t;
memset(hp,0x3f,sizeof(hp));
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=n;i++){
ll t;
cin>>t>>h[i];
at[i]=t;
mx=max(mx,t);
hp[t]=min(hp[t],h[i]);
}
for(int i=1;i<=1e5;i++){
if(hp[i]>1e5)continue;
for(int j=1;j*j<=hp[i];j++){
if(hp[i]%j)continue;
e[j].push_back({i,1ll*((hp[i]-1)/j-((hp[i]-1)/mx))*i});
if(j*j!=hp[i])e[(hp[i]-1)/j+1].push_back({i,1ll*(j-1-((hp[i]-1)/mx))*i});
}
}
priority_queue<pii,vector<pii>,greater<pii>>q;
int now=0;
q.push({0,t});
dis[t]=0;
while(!q.empty()){
int u=q.top().second;
ll d=q.top().first;
q.pop();
if(u<=now||dis[u]<d)continue;
int lst=now;
now=u;
for(int i=lst+1;i<=u;i++){
for(auto t:e[i]){
if(dis[t.v]>t.w+dis[u]){
dis[t.v]=t.w+dis[u];
q.push({t.w+dis[u],t.v});
}
}
}
}
ll ans=dis[mx];
// for(int i=1;i<=5;i++)cout<<dis[i]<<"\n";
for(int i=1;i<=n;i++)ans=ans+1ll*((h[i]-1)/mx)*at[i];
cout<<ans<<"\n";
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t=1;
// cin>>t;
while(t--)solve();
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 8216kb
input:
4 1 3 2 4 4 5 6 1 6
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 16ms
memory: 11120kb
input:
5000 679 84191 46042 81916 66659 74636 72443 10252 57443 21838 54620 84896 58466 20832 29643 45949 20576 50399 51434 56472 90759 68909 94348 39459 1731 81207 17614 26465 11775 93861 24936 25017 64663 21042 37570 32903 68583 68840 58347 93849 10841 10190 77131 10595 1959 57163 59047 16066 89850 73741...
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 3ms
memory: 10888kb
input:
5000 685 67283 21828 19841 367 69908 57925 63894 10753 20139 20595 672 47788 81010 57483 53755 96758 85049 78636 94198 12795 97299 86489 57399 56590 30519 63514 92072 5714 60572 8651 25620 13514 27482 51652 88352 27272 4391 23458 43759 57471 95084 88191 53782 96875 52546 33731 95458 5643 75049 42685...
output:
60515
result:
ok single line: '60515'
Test #4:
score: 0
Accepted
time: 16ms
memory: 11052kb
input:
5000 883 57988 4889 27548 3497 47774 97848 73725 83535 43075 12741 86312 87522 98386 29435 88105 19813 50656 83340 32721 37465 84421 14671 92169 37187 33163 53370 95155 35577 63396 86337 20931 57282 80964 12797 84905 95122 7530 7623 1393 58436 9609 91063 92309 31959 37789 98189 74209 33091 64400 530...
output:
142420
result:
ok single line: '142420'
Test #5:
score: 0
Accepted
time: 15ms
memory: 10960kb
input:
5000 110 81857 71124 57698 64343 80952 96284 15190 95432 51153 64223 39943 25603 77013 72711 94708 24951 64786 9225 54307 29867 2166 9420 38155 28813 96118 90751 85381 30858 17457 43971 38450 20480 36831 31955 86436 3116 71718 45322 2141 92627 36585 66945 8885 99790 49929 5604 25126 14766 78673 4804...
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 11ms
memory: 10176kb
input:
5000 852 68512 97389 60972 88659 73325 90709 87906 83485 39089 40758 25295 95321 61154 18959 19137 97232 40721 17563 3359 33010 484 29851 3964 60841 88065 81476 1622 35273 28703 97697 72577 9099 16043 92977 37261 95232 41086 16776 38139 94039 79650 24363 30987 95332 81397 67793 52508 71034 22631 725...
output:
0
result:
ok single line: '0'
Test #7:
score: -100
Wrong Answer
time: 20ms
memory: 15112kb
input:
5000 23 49957 100000 97978 100000 66997 100000 70406 100000 62250 100000 71093 100000 14758 100000 59859 100000 81605 100000 50139 100000 97303 100000 23626 100000 38523 100000 5028 100000 59461 100000 99559 100000 5150 100000 21343 100000 5738 100000 81487 100000 87427 100000 67101 100000 8692 1000...
output:
251847582
result:
wrong answer 1st lines differ - expected: '251733189', found: '251847582'