Submission #1276868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276868		boclobanchat	Ski 2 (JOI24_ski2)	C++20	86 / 100	1847 ms	2032 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=333;
const long long INF=1e18;
const long long MXV=1e15;
long long dp[2][MAXN][MAXN];
int len[MAXN*2],cnt[MAXN*2],pos[MAXN*2],val[MAXN],pref[MAXN*2];
pair<int,int> A[MAXN];
bool ck[MAXN];
void reset(int p,int n)
{
	for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[p][i][j]=INF;
}
void minimize(long long& a,long long b)
{
	if(a>b) a=b;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	long long n,p;
	cin>>n>>p;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i].first>>A[i].second;
		val[i]=A[i].first;
	}
	sort(val+1,val+n+1);
	sort(A+1,A+n+1);
	int mn=2e9,m=0;
	for(int i=0;i<=n*2;i++) pref[i]=2e9;
	for(int i=1;i<=n;i++) if(i==1||val[i]!=val[m]) val[++m]=val[i];
	for(int i=1;i<=n;i++) if(mn>A[i].second) mn=A[i].second,pref[(lower_bound(val+1,val+m+1,A[i].first)-val)*2-1]=A[i].second;
	else cnt[(lower_bound(val+1,val+m+1,A[i].first)-val)*2-1]++;
	for(int i=1;i<=m;i++)
	{
		len[i*2-1]=1,pos[i*2-1]=val[i],pos[i*2]=val[i]+1;
		if(i<m) len[i*2]=val[i+1]-val[i]-1;
		else len[i*2]=n+69;
	}
	for(int i=1;i<=m*2;i++) pref[i]=min(pref[i],pref[i-1]);
	reset(0,n);
	reset(1,n);
	dp[0][0][1]=0;
	int sum=0;
	for(int i=1;i<=m*2;i++)
	{
		int a=i%2,b=1-a;
		reset(a,n);
		sum+=cnt[i];
		long long v=1LL*pos[i]*cnt[i]*p;
		for(int k=1;k<=n;k++) for(int j=sum;j+1;j--)
		{
			if(j>=cnt[i]) minimize(dp[a][j][k],dp[b][j-cnt[i]][k]-v);
			if(i>1&&j>=cnt[i]&&dp[b][j-cnt[i]][k]<=MXV)
			{
				long long mxv=1LL*len[i]*k;
				if(pref[i]!=pref[i-1]) mxv=1LL*len[i]*(k-1);
				mxv=min(mxv,1LL*j);
				long long sum=dp[b][j-cnt[i]][k]-v,w=p*pos[i];
				int cc=0;
				for(int c=1;c<=mxv&&sum<=MXV;c++)
				{
					sum+=w;
					if(++cc==k) cc=0,w+=p;
					minimize(dp[a][j-c][k],sum);
				}
			}
			if(i>1&&k<n&&dp[a][j][k]<=MXV)
			{
				long long sum=dp[a][j][k]+pref[i-1],w=p*pos[i];
				for(int x=1;x<=len[i]&&x<=j&&sum<=MXV;x++) minimize(dp[a][j-x][k+1],(sum+=w)),w+=p;
			}
		}
	}
	long long ans=INF;
	for(int i=0;i<=n;i++) minimize(ans,dp[0][0][i]);
	cout<<ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 33 / 33
• Subtask 5: 27 / 27
• Subtask 6: 0 / 14