Submission #988470

#	Time	Username	Problem	Language	Result	Execution time	Memory
988470		amirhoseinfar1385	Ski 2 (JOI24_ski2)	C++17	100 / 100	773 ms	3672 KiB

Main

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
const long long maxn=305,maxh=606;
long long n,k,mn[maxn],sum[maxn],cnt[maxn],vis[maxn],inf=1e17,last[maxn],suf[maxn];
long long dp[2][maxn+10][maxn*2+10],mid=maxn+2;
vector<pair<long long ,long long>>all;
bool cmp(pair<long long ,long long> a,pair<long long ,long long> b){
	if(a.first!=b.first){
		return a.first<b.first;
	}
	return a.second<b.second;
}
long long fres=0;

void vorod(){
	cin>>n>>k;
	if(n==1){
		cout<<0<<endl;
		exit(0);
	}
	all.resize(n);
	
	for(long long i=0;i<n;i++){
		cin>>all[i].first>>all[i].second;
		all[i].first++;
	}
	sort(all.begin(),all.end(),cmp);
	for(long long i=1;i<n;i++){
		if(all[i].first==all[0].first){
			all[i].first++;
			fres+=k;
		}
	}
	for(int i=1;i<n;i++){
		all[i].first-=all[0].first;
	}
	all[0].first=0;
	long long ted=1;
	vector<long long>fa(n);
	fa[0]=all[0].first;
	for(int i=1;i<n;i++){
		if(all[i].first!=all[i-1].first){
			fa[i]=fa[i-1]+min(ted,all[i].first-all[i-1].first);
			ted=1+max(0ll,ted-(all[i].first-all[i-1].first));
		}else{
			ted++;
			fa[i]=fa[i-1];
		}
	}
	for(int i=0;i<n;i++){
		all[i].first=fa[i]+1;
	}
	for(long long i=0;i<maxn;i++){
		mn[i]=inf;
	}
	for(long long i=0;i<n;i++){
		mn[all[i].first]=min(mn[all[i].first],all[i].second);
		cnt[all[i].first]++;
	}
	suf[maxn-1]=cnt[maxn-1];
	for(int i=maxn-2;i>=0;i--){
		suf[i]=suf[i+1]+cnt[i];
	}
	for(long long i=1;i<maxn;i++){
		mn[i]=min(mn[i],mn[i-1]);
	}
}

void solve(){
	for(long long i=0;i<2;i++){
		for(long long j=0;j<maxn;j++){
			for(long long h=0;h<maxn;h++){
				dp[i][j][h]=inf;
			}
		}
	}
	dp[1][cnt[all[1].first]][1]=0;
	long long mainres=inf;
	for(long long i=all[1].first;i<maxn-1;i++){
		for(long long j=0;j<maxn;j++){
			for(long long h=0;h<maxn;h++){
				if(dp[1][j][h]==inf){
					continue;
				}
				if(suf[i+1]==0&&j==0){
					mainres=min(mainres,dp[1][j][h]);
					//continue;
				}
				for(long long z=1-(j==0);z<=j;z++){
					long long fake=max(0ll,z-h)*mn[i-1]+(j-z)*k;
					dp[0][cnt[i+1]+(j-z)][max(0ll,h-z)+z]=min(dp[0][cnt[i+1]+(j-z)][max(0ll,h-z)+z],dp[1][j][h]+fake);
				}
			}
		}
		for(long long j=0;j<maxn;j++){
			for(long long h=0;h<maxn;h++){
				swap(dp[1][j][h],dp[0][j][h]);
				dp[0][j][h]=inf;
			}
		}
	}
//	for(long long i=0;i<maxn;i++){
//		mainres=min(mainres,dp[1][0][i]);
//	}
	mainres+=fres;
	cout<<mainres<<endl;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
//	freopen("inp.txt","r",stdin);
	vorod();
//	pre();
	solve();
//	khor();
}

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