QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672402 | #7078. Tower of the Sorcerer | Soestx | WA | 1ms | 9792kb | C++23 | 1.8kb | 2024-10-24 16:43:47 | 2024-10-24 16:43:47 |
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;
for(int i=id;i<=M;i+=lowbit(i))
{
if(bit[i]>x) bit[i]=x;
}
}
int quer(int l,int r)
{
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);
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;
}
/*
*/
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 9792kb
input:
4 1 3 2 4 4 5 6 1 6
output:
17
result:
wrong answer 1st lines differ - expected: '9', found: '17'