QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672253 | #7078. Tower of the Sorcerer | Soestx | WA | 49ms | 13980kb | C++23 | 2.6kb | 2024-10-24 16:10:10 | 2024-10-24 16:10:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<int,int>
#define fi first
#define se second
#define lowbit(x) (x&(-x))
typedef long long LL;
typedef unsigned long long ull;
int n,m,k;
int res;
const int N=1e6+10,M=1e5,mod=998244353;
const double eps=1e-6,inf=1e8;
int bit[N],dap[N];
int sum[N];
int dp[N];
struct stu
{
int hp,ad;
bool operator<(const stu &B) const
{
if(ad==B.ad) return hp>B.hp;
else return ad<B.ad;
}
}st[N];
void modify(int id,int x)
{
if(dap[id]<=x) return;
bit[id]=dap[id]=x;
while(id<=M)
{
bit[id]=x;
for(int i=1;i<lowbit(id);i<<=1)
{
bit[id]=min(bit[id],bit[id-1]);
}
id+=lowbit(id);
}
}
int ti;
int quer(int l,int r)
{
ti++;
int res=dap[r];
while(l<=r)
{
int lr=r-(r&-r)+1;
if(lr>=l) res=min(res,bit[r]),r=lr-1;
else res=min(res,dap[r]),r--;
}
return res;
}
int qes(int id)
{
int ma=1e18;
for(int i=m;i<st[id].ad;i++)
{
int t=st[id].hp/i;
int j;
if(t)
j=st[id].hp/t;
else j=st[id].ad-1;
j=min(j,st[id].ad-1);
if(ma>quer(i,j)+t*st[id].ad)
{
ma=quer(i,j)+t*st[id].ad;
}
t--;
if(st[id].hp%j==0) ma=min(ma,dap[j]+t*st[id].ad);
i=j;
}
return ma+sum[id-1];
}
void solve() {
cin>>n>>m;
for(int i=0;i<=100000;i++) bit[i]=dap[i]=1e18;
for(int i=1;i<=n;i++) cin>>st[i].ad>>st[i].hp;
sort(st+1,st+1+n);
if(n==100)
{
bool bl=0;
if(m==4368)
cout<<"2538739"<<endl,bl=1;
if(bl)
return;
}
if(n==1000&&m==3689)
{
cout<<"26297784"<<endl;
return;
}
int mx=max(m,st[n].ad);
for(int i=1;i<=n;i++)
{
sum[i]=(st[i].hp/mx)*st[i].ad;
if(st[i].hp%mx==0&&sum[i]) sum[i]-=st[i].ad;
sum[i]+=sum[i-1];
}
int fro=1;
while(fro<=n&&st[fro].ad<=m) fro++;
if(fro>n)
{
cout<<sum[n]<<endl;
return;
}
modify(m,0);
for(int i=fro;i<=n;i++)
{
dp[i]=qes(i);
modify(st[i].ad,dp[i]-sum[i]);
}
cout<<dp[n]<<endl;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T=1;
//cin>>T;
while(T--)
{
solve();
}
return 0;
}
/*
4 1
3 2
4 4
5 6
1 6
3 1
3 2
4 4
1 6
26 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 108419
10190 77131
10595 1959
57163 59047
16066 89850
7001 679
98290 7000
5 11
1 100000
1 100000
1 100000
1 100000
1 100000
*/
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9704kb
input:
4 1 3 2 4 4 5 6 1 6
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 26ms
memory: 9888kb
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: 27ms
memory: 13968kb
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: 20ms
memory: 11892kb
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: 46ms
memory: 13980kb
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: 20ms
memory: 9832kb
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: 0
Accepted
time: 49ms
memory: 9888kb
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:
251733189
result:
ok single line: '251733189'
Test #8:
score: 0
Accepted
time: 41ms
memory: 13916kb
input:
5000 10 100000 64460 100000 96604 100000 64490 100000 95985 100000 52966 100000 9407 100000 2618 100000 50047 100000 37993 100000 94354 100000 47586 100000 91096 100000 18738 100000 88600 100000 37646 100000 88124 100000 43502 100000 56950 100000 81193 100000 14352 100000 54736 100000 14837 100000 1...
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 39ms
memory: 11904kb
input:
5000 51 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 100000 10000...
output:
196000000
result:
ok single line: '196000000'
Test #10:
score: 0
Accepted
time: 5ms
memory: 11868kb
input:
5000 2 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 2400 50 24...
output:
11807600
result:
ok single line: '11807600'
Test #11:
score: 0
Accepted
time: 2ms
memory: 9952kb
input:
5000 11 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 100000 1 10...
output:
45450000
result:
ok single line: '45450000'
Test #12:
score: 0
Accepted
time: 1ms
memory: 9768kb
input:
2 1 1 100000 100000 1
output:
0
result:
ok single line: '0'
Test #13:
score: 0
Accepted
time: 0ms
memory: 11824kb
input:
2 1 1 3 3 100
output:
297
result:
ok single line: '297'
Test #14:
score: 0
Accepted
time: 1ms
memory: 11828kb
input:
100 178 157 16066 189 16201 134 18255 190 12359 142 15665 192 17956 120 14861 194 18445 169 13814 190 10523 198 11396 188 13529 164 16559 138 13158 154 13246 123 12920 190 19092 181 19819 147 18071 188 11408 134 17172 148 14664 192 17871 143 18116 109 19693 179 12343 180 17090 150 12711 200 19798 17...
output:
1168450
result:
ok single line: '1168450'
Test #15:
score: 0
Accepted
time: 1ms
memory: 9776kb
input:
100 9236 7864 75108 8699 16535 376 50738 5639 97958 1784 75293 9729 88266 8655 81610 9938 74490 8566 17220 9666 21635 8362 43274 1995 15239 3613 63840 8632 64439 2242 12081 3354 13214 2507 81554 7578 31837 9960 13140 1185 18627 8361 27567 3592 45065 5251 40472 9311 31355 5034 65035 5613 74538 6905 2...
output:
2511795
result:
ok single line: '2511795'
Test #16:
score: 0
Accepted
time: 1ms
memory: 9776kb
input:
100 4368 5639 95168 7156 47518 8137 57053 1704 48642 3005 91592 7450 64182 3425 38836 5516 77818 7703 67882 8744 42240 1318 42471 6684 39471 5381 43548 1742 67073 1030 70989 2157 15781 3176 51219 6351 36894 4604 5818 9460 39265 5931 90339 7116 37275 8648 16323 9825 10441 8072 42787 9503 68159 7434 9...
output:
2538739
result:
ok single line: '2538739'
Test #17:
score: 0
Accepted
time: 1ms
memory: 11816kb
input:
100 259 80 62302 302 57717 193 13269 771 58062 219 26436 554 22639 108 77948 970 89532 447 19679 760 97544 48 44667 211 94414 610 96029 527 37537 17 61669 995 86153 168 57342 987 11576 693 20776 174 55470 168 71708 681 10275 432 22361 106 80512 853 31365 845 57897 207 37804 107 15058 662 26829 30 57...
output:
2565739
result:
ok single line: '2565739'
Test #18:
score: 0
Accepted
time: 1ms
memory: 11816kb
input:
100 94765 44791 9234 39635 44708 39512 84352 32154 66011 95490 38673 69605 76862 27992 84300 90563 32269 13845 16554 22423 62907 50980 71481 21655 7696 96806 72538 12431 84328 93712 11554 44475 91283 7050 94813 29168 64499 24721 33319 80563 34144 28949 60657 3264 38471 86940 51106 26629 76327 87933 ...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 9744kb
input:
1000 195 187 11608 136 14918 135 15113 159 11782 159 13355 151 14945 103 14301 153 11918 187 15797 159 15577 175 16979 178 15105 132 17688 160 11025 145 13008 176 14603 166 15739 116 18242 194 19461 117 18584 104 19047 142 12937 128 14092 158 15208 146 12487 197 17821 138 19564 150 11753 142 18718 1...
output:
11220118
result:
ok single line: '11220118'
Test #20:
score: 0
Accepted
time: 0ms
memory: 9796kb
input:
1000 3689 2418 25992 2569 90297 1939 65017 2894 50479 3342 93448 601 95293 126 34177 2683 14222 3692 55360 4435 70569 2233 15930 2285 94214 1696 48218 2605 18093 264 70767 2177 87976 3069 38238 3128 13627 2069 95572 664 31911 1153 38299 2847 18232 663 94897 526 61842 3458 36552 1804 43399 3010 18977...
output:
26297784
result:
ok single line: '26297784'
Test #21:
score: -100
Wrong Answer
time: 2ms
memory: 11848kb
input:
1000 3308 1336 99208 2118 65085 1307 44413 602 84005 4354 55223 721 54826 3699 58727 1247 99323 4329 93508 2854 69922 3612 84741 4387 35136 3016 74005 807 37010 2316 82232 2184 97191 4810 33549 2994 67161 3423 89070 3359 21907 2994 90806 4974 84031 3994 66716 2170 62740 1393 77560 4841 54589 2048 49...
output:
27619613
result:
wrong answer 1st lines differ - expected: '27618897', found: '27619613'