QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#672402#7078. Tower of the SorcererSoestxWA 1ms9792kbC++231.8kb2024-10-24 16:43:472024-10-24 16:43:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 16:43:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9792kb
  • [2024-10-24 16:43:47]
  • 提交

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'