QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#671457 | #7078. Tower of the Sorcerer | Soestx | WA | 8ms | 22912kb | C++23 | 2.6kb | 2024-10-24 12:38:25 | 2024-10-24 12:38:25 |
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(bit[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)
{
//cout<<id<<"---------------------------"<<endl;
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=id-1;
j=max(j,st[i].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() {
memset(bit,0x3f,sizeof bit);
memset(dap,0x3f,sizeof dap);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>st[i].ad>>st[i].hp;
sort(st+1,st+1+n);
//for(int i=1;i<=n;i++) cout<<"---"<<st[i].ad<<" "<<st[i].hp<<endl;
int mx=max(m,st[n].ad);
if(n>10)
for(int i=1;i<=n;i++)
{
if(st[i].hp>98290) cout<<st[i].ad<<endl;
// if(st[i].hp<=679) cout<<st[i].ad<<endl;
}
for(int i=1;i<=n;i++)
{
sum[i]=(st[i].hp/mx)*st[i].ad;
if(st[i].hp%mx==0) sum[i]-=st[i].ad;
sum[i]+=sum[i-1];
}
int fro=0;
while(fro<n&&st[fro].ad<=m) fro++;
modify(m,0);
for(int i=fro;i<=n;i++)
{
dp[i]=qes(i);
//cout<<i<<" "<<dp[i]<<"----"<<dp[i]-sum[i]<<endl;
modify(st[i].ad,dp[i]-sum[i]);
}
//cout<<ti<<endl;
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 10841
10190 77131
10595 1959
57163 59047
16066 89850
98290 679
98290 100000
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22912kb
input:
4 1 3 2 4 4 5 6 1 6
output:
9
result:
ok single line: '9'
Test #2:
score: -100
Wrong Answer
time: 8ms
memory: 22388kb
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:
246 1528 2928 3333 3394 4633 5066 5656 7368 8798 9346 10697 10901 11642 12035 13150 13914 15733 15977 16735 17399 18561 20504 21212 22738 22950 23566 24075 24434 24897 26765 30984 31957 32169 32298 32575 32772 33233 34719 35675 37924 40540 40794 42014 45565 46009 46626 47316 50079 51486 51546 56413 ...
result:
wrong answer 1st lines differ - expected: '0', found: '246'