Submission #684704

#	Time	Username	Problem	Language	Result	Execution time	Memory
684704		penguin133	Safety (NOI18_safety)	C++17	100 / 100	180 ms	22492 KiB

safety

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif

int S[200005], n, h;
void solve(){
	cin >> n >> h;
	for(int i=1;i<=n;i++)cin >> S[i];
	
	multiset <int> lft, rgt;
	int lft_os = 0, rgt_os = 0, ans = 0;
	for(int i=1;i<=n;i++){
		if(i != 1)rgt_os += h;
		//if(i != 1)lft_os += (R[i] - L[i]);	
		int rmost = (lft.empty() ? -1e18 : *--lft.end() - lft_os);
		int lmost = (rgt.empty() ? 1e18 : *rgt.begin() + rgt_os);
		//cerr << rmost << " " << lmost << '\n';
		assert(rmost <= lmost);
		if(S[i] < rmost){
			lft.insert(S[i] + lft_os);
			lft.insert(S[i] + lft_os);
			int rmost2 = (lft.empty() ? -1e18 : *--lft.end() - lft_os);
			int lmost2 = (rgt.empty() ? 1e18 : *rgt.begin() + rgt_os);
			//cout << min(abs(R[i] - lmost2), abs(R[i] - rmost2)) << '\n';
			ans += min(abs(S[i] - lmost2), abs(S[i] - rmost2));
			lft.erase(--lft.end());
			assert(rmost2 - rgt_os <= *rgt.begin());
			rgt.insert(rmost2 - rgt_os);
		}
		else if(S[i] > lmost){
			rgt.insert(S[i] - rgt_os);
			rgt.insert(S[i] - rgt_os);
			int lmost2 = (rgt.empty() ? 1e18 : *rgt.begin() + rgt_os);
			int rmost2 = (lft.empty() ? -1e18 : *--lft.end() - lft_os);
			ans += min(abs(S[i] - lmost2), abs(S[i] - rmost2));
			//cout << min(abs(R[i] - lmost2), abs(R[i] - rmost2)) << '\n';
			rgt.erase(rgt.begin());
			assert(lmost2 + lft_os >= *--lft.end());
			lft.insert(lmost2 + lft_os);
		}
		else{
			lft.insert(S[i] + lft_os);
			rgt.insert(S[i] - rgt_os);
		}
		lft_os += h;	
		/*
		int rmost2 = (lft.empty() ? -1e18 : *--lft.end() - lft_os);
		int lmost2 = (rgt.empty() ? 1e18 : *rgt.begin() + rgt_os);
		ans += min(abs(R[i] - lmost2), abs(R[i] - rmost2));
		*/
	}
	cout << ans << '\n';
}

/*
 * so let dp(i, j) represent minimum cost to connect first i rows, with right end of rectangle i being at j
 * let range of rectangle i - 1 be x,  range of rect i be y
 * dp(i, j) = min(dp(i-1, k) such that j - y <= k <= j + x) + |j - R[i]|
 * 
 * we have some offset
 */
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

safety.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main(){
      | ^~~~

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29