제출 #1120075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1120075		Math4Life2020	Ski 2 (JOI24_ski2)	C++17	86 / 100	538 ms	510196 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 = 700; const ll INF = 2e18;

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

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];
	}
	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: 0 / 14