제출 #1276866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276866		boclobanchat	Ski 2 (JOI24_ski2)	C++20	86 / 100	2093 ms	3748 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=333;
const __int128 INF=1e25;
const __int128 MXV=1e23;
__int128 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(__int128& a,__int128 b)
{
	if(a>b) a=b;
}
__int128 f(__int128 n,__int128 p,__int128 k)
{
	return n*k+p*k*(k-1)/2;
}
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];
		__int128 v=(__int128)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);
				for(int c=1;c<=mxv&&c<=j;c++) minimize(dp[a][j-c][k],dp[b][j-cnt[i]][k]-v+f(p*pos[i],p,c/k)*k+(pos[i]+c/k)*p*(c%k));
			}
			if(i>1&&k<n&&dp[a][j][k]<=MXV) for(int x=1;x<=len[i]&&x<=j;x++) minimize(dp[a][j-x][k+1],dp[a][j][k]+f(p*pos[i],p,x)+pref[i-1]);
		}
	}
	__int128 ans=INF;
	for(int i=0;i<=n;i++) minimize(ans,dp[0][0][i]);
	string res;
	if(!ans) res="0";
	while(ans) res+=char(ans%10+'0'),ans/=10;
	reverse(res.begin(),res.end());
	cout<<res;
}

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