Submission #1120076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120076		Math4Life2020	Ski 2 (JOI24_ski2)	C++17	100 / 100	733 ms	728784 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 305; const ll Hm = 1000; const ll INF = 2e18;

ll dp[Hm][Nm][Nm];
//height being processed
//current flow
//available pull requests

vector<ll> prc(vector<ll> v0) {
	ll N = v0.size();
	vector<ll> vf;
	for (ll i=0;i<N;i++) {
		vf.push_back(-1);
	}
	vector<pii> v1;
	ll hmin = INF;
	for (ll i=0;i<N;i++) {
		hmin = min(hmin,v0[i]);
	}
	for (ll i=0;i<N;i++) {
		v1.push_back({v0[i]-hmin,i});
	}
	sort(v1.begin(),v1.end());
	vector<pii> v2;
	
	ll i1 = 0; //index of 1
	ll x1; //x of the current 1-term
	ll xc = 0; //current (true) x-value
	ll del = 0; //amount to delete from each coming term
	ll amt = 0; //amortized tracker
	while (i1<N) {
		x1 = v1[i1].first;
		if (x1==xc) {
			amt++;
			v2.push_back({v1[i1].first-del,v1[i1].second});
			i1++;
		} else {
			xc++;
			amt--;
			if (amt<0) {
				amt=0; del += (x1-xc); xc=x1;
			}
		}
	}
	for (pii p0: v2) {
		vf[p0.second]=p0.first;
	}
	return vf;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,K; cin >> N >> K;
	ll ans = 0;
	ll H0[N]; ll C0[N];
	for (ll i=0;i<N;i++) {
		cin >> H0[i] >> C0[i];
	}
	vector<ll> h0copy;
	for (ll i=0;i<N;i++) {
		h0copy.push_back(H0[i]);
	}
	h0copy = prc(h0copy);
	for (ll i=0;i<N;i++) {
		H0[i]=h0copy[i];
	}
	ll n0[Hm];
	ll psn0[Hm+1];
	psn0[0]=0;
	ll cmin[Hm];
	for (ll i=0;i<Hm;i++) {
		cmin[i]=INF;
		n0[i]=0;
	}
	for (ll i=0;i<N;i++) {
		n0[H0[i]]++;
		cmin[H0[i]]=min(C0[i],cmin[H0[i]]);
	}
	ll hmin = INF; 
	for (ll h=0;h<Hm;h++) {
		if (n0[h]!=0) {
			hmin = h;
			n0[h+1]+=(n0[h]-1);
			ans += K*(n0[h]-1);
			n0[h]=1;
			break;
		}
	}
	for (ll h=0;h<(Hm-hmin);h++) {
		n0[h]=n0[h+hmin];
		cmin[h]=cmin[h+hmin];
	}
	for (ll h=0;h<Hm;h++) {
		psn0[h+1]=psn0[h]+n0[h];
	}
	for (ll i=0;i<Hm;i++) {
		for (ll j=0;j<Nm;j++) {
			for (ll k=0;k<Nm;k++) {
				dp[i][j][k]=INF;
			}
		}
	}
	dp[0][0][1]=0;
	ll rmin = INF; //rolling cmin
	for (ll h=0;h<(Hm-1);h++) {
		ll n0v = n0[h];
		for (ll f=0;f<Nm;f++) {
			for (ll p=1;p<Nm;p++) {
				if (dp[h][f][p]>=INF) {
					continue;
				}
				ll xn = n0v+f;
				if (xn>p) {
					dp[h+1][xn-p][p]=min(dp[h+1][xn-p][p],dp[h][f][p]+K*(xn-p));
				} else {
					dp[h+1][0][p]=min(dp[h+1][0][p],dp[h][f][p]);
				}
			}
		}
		rmin = min(rmin,cmin[h]);
		for (ll f=0;f<Nm;f++) {
			for (ll p=0;p<(Nm-1);p++) {
				dp[h+1][f][p+1]=min(dp[h+1][f][p+1],dp[h+1][f][p]+rmin);
			}
		}
	}
	//process DP
	ll ansf = INF;
	for (ll j=0;j<Nm;j++) {
		ansf = min(ansf,dp[Hm-1][0][j]);
	}
	cout << (ans+ansf)<<"\n";
}

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